Sublinear geometric algorithms

Bernard Chazelle, Ding Liu, Avner Magen

Research output: Contribution to journalArticle

24 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 triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected 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)627-646
Number of pages20
JournalSIAM Journal on Computing
Volume35
Issue number3
DOIs
StatePublished - Dec 1 2005

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Approximate shortest paths
  • Polyhedral intersection
  • Sublinear algorithms

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

  • Cite this