Abstract
Let B be any finite set of pairwise-disjoint, axes-parallel boxes in Euclidean d-space. Our main theorem is that for any two points s, t not in the interior of B, there exists a coordinate direction φ such that every rectilinear B-avoiding shortest path is monotone along φ. The key concept in the proof is an appropriate notion of pyramids.
Original language | English (US) |
---|---|
Pages | 339-348 |
Number of pages | 10 |
State | Published - 1996 |
Event | Proceedings of the 1996 12th Annual Symposium on Computational Geometry - Philadelphia, PA, USA Duration: May 24 1996 → May 26 1996 |
Other
Other | Proceedings of the 1996 12th Annual Symposium on Computational Geometry |
---|---|
City | Philadelphia, PA, USA |
Period | 5/24/96 → 5/26/96 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics