Local polyhedra and geometric graphs

Research output: Contribution to conferencePaperpeer-review


We introduce a new realistic input model for geometric graphs and nonconvex polyhedra. A geometric graph G is local if (1) the longest edge at every vertex v is only a constant factor longer than the distance from v to its Euclidean nearest neighbor and (2) the lengths of the longest and shortest edges differ by at most a polynomial factor. A polyhedron is local if all its faces are simplices and its edges form a local geometric graph. We show that any boolean combination of any two local polyhedra in ℝd each with n vertices, can be computed in O(n log n) time, using a standard hierarchy of axis-aligned bounding boxes. Using results of de Berg, we also show that any local polyhedron in ℝd has a binary space partition tree of size O(n logd-1 n). Finally, we describe efficient algorithms for computing Minkowski sums of local polyhedra in two and three dimensions.

Original languageEnglish (US)
Number of pages10
StatePublished - 2003
EventNineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States
Duration: Jun 8 2003Jun 10 2003


OtherNineteenth Annual Symposium on Computational Geometry
Country/TerritoryUnited States
Citysan Diego, CA


  • Binary space partition
  • Bounding volume hierarchies
  • Collision detection
  • Realistic input models

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Local polyhedra and geometric graphs'. Together they form a unique fingerprint.

Cite this