TY - JOUR

T1 - Local polyhedra and geometric graphs

AU - Erickson, Jeff

N1 - Funding Information:
✩ A preliminary version of this paper was presented at the 19th Annual ACM Symposium on Computational Geometry, 2003, pp. 171–180. See http://www.cs.uiuc.edu/~jeffe/pubs/local.html for the most recent version of this paper. E-mail address: jeffe@cs.uiuc.edu (J. Erickson). URL: http://www.cs.uiuc.edu/~jeffe. 1 Partially supported by a Sloan Foundation Fellowship, NSF CAREER award CCR-0093348, and NSF ITR grants DMR-0121695 and CCR-0219594. Portions of this work were done while the author was visiting Duke University.

PY - 2005/5

Y1 - 2005/5

N2 - We introduce a new realistic input model for straight-line 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 among the other vertices of G and (2) the longest and shortest edges of G differ in length 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 two local polyhedra in Rd, each with n vertices, can be computed in O(nlogn) time using a standard hierarchy of axis-aligned bounding boxes. Using results of de Berg, we also show that any local polyhedron in Rd has a binary space partition tree of size O(nlogd- 2n) and depth O(logn); 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.

AB - We introduce a new realistic input model for straight-line 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 among the other vertices of G and (2) the longest and shortest edges of G differ in length 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 two local polyhedra in Rd, each with n vertices, can be computed in O(nlogn) time using a standard hierarchy of axis-aligned bounding boxes. Using results of de Berg, we also show that any local polyhedron in Rd has a binary space partition tree of size O(nlogd- 2n) and depth O(logn); 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.

KW - Binary space partition

KW - Bounding volume hierarchy

KW - Intersection detection

KW - Minkowski sum

KW - Realistic input model

UR - http://www.scopus.com/inward/record.url?scp=84867975392&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867975392&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2004.08.004

DO - 10.1016/j.comgeo.2004.08.004

M3 - Article

AN - SCOPUS:84867975392

VL - 31

SP - 101

EP - 125

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

IS - 1-2

ER -