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: [email protected] (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
SN - 0925-7721
VL - 31
SP - 101
EP - 125
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 1-2
ER -