## Abstract

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 log^{d-1} n). Finally, we describe efficient algorithms for computing Minkowski sums of local polyhedra in two and three dimensions.

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

Pages | 171-180 |

Number of pages | 10 |

DOIs | |

State | Published - 2003 |

Event | Nineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States Duration: Jun 8 2003 → Jun 10 2003 |

### Other

Other | Nineteenth Annual Symposium on Computational Geometry |
---|---|

Country/Territory | United States |

City | san Diego, CA |

Period | 6/8/03 → 6/10/03 |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics