Sublinear geometrie algorithms

Bernard Chazelle, Ding Liu, Avner Magen

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional Delaunay triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.

Original languageEnglish (US)
Pages (from-to)531-540
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Aug 1 2003

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Sublinear geometrie algorithms'. Together they form a unique fingerprint.

Cite this