### Abstract

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- ^{2}n) 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.

Original language | English (US) |
---|---|

Pages (from-to) | 101-125 |

Number of pages | 25 |

Journal | Computational Geometry: Theory and Applications |

Volume | 31 |

Issue number | 1-2 |

DOIs | |

State | Published - May 1 2005 |

### Keywords

- Binary space partition
- Bounding volume hierarchy
- Intersection detection
- Minkowski sum
- Realistic input model

### ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics