Sublinear geometrie algorithms

Bernard Chazelle, Ding Liu, Avner Magen

Research output: Contribution to journalConference articlepeer-review

16 Scopus citations


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 - 2003
Event35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003

All Science Journal Classification (ASJC) codes

  • Software


  • Approximate shortest paths
  • Polyhedral intersection
  • Sublinear algorithms


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

Cite this