Local polyhedra and geometric graphs

Proceedings of the 19th Annual ACM Symposium on Computational Geometry, 171-180, 2003.

• Download submitted journal version:

• Download SOCG version (© 2003 ACM):
• Official SoCG version from ACM's digital library (subscription or $5 payment required)

Abstract:

We introduce a new realistic input model for geometric graphs and nonconvex polyhedra. A geometric graph 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 R^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 R^d has a binary space partition tree of size O(n log^d-2 n) and depth O(log n); these bounds are tight in the worst case when d≤3. Finally, we describe efficient algorithms for computing Minkowski sums of local polyhedra in two and three dimensions.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 14 Sep 2004