Sublinear Geometric Algorithms

Bernard Chazelle, Ding Liu, Avner Magen

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

Abstract

We initiate an investigation of sublinear algorithms for geometric problems in two and three dimen-sions. 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)
JournalDagstuhl Seminar Proceedings
Volume5291
StatePublished - 2006
EventSublinear Algorithms 2005 - Wadern, Germany
Duration: Jul 17 2005Jul 22 2005

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Sublinear Geometric Algorithms'. Together they form a unique fingerprint.

Cite this