Rectilinear geodesics in 3-space (extended abstract)
Joonsoo Choi, Chee-Keng Yap · 1995
) Joonsoo Choi Chee-Keng Yap Courant Institute of Mathematical Sciences New York University 251, Mercer Street New York, NY 10012 Abstract Let B be any finite set of pairwise-disjoint, axes-parallel boxes in Euclidean 3-space. Our main theorem is that for any two points s; t 62 [B, there exists a shortest rectilinear B-avoiding path from s to t that is monotone along at least one of the axes. The key concept in the proof is an appropriate notion of pyramids. Exploiting this result algorithmically, we obtain: a L1 shortest distance from a query point to a fixed source point can be computed in O(log n) time after O(n 2 log n) time preprocessing, where n is the number of boxes. and also de Berg et al [dBvKNO92] when their results are specialized to disjoint obstacles. 1 Introduction The geometric shortest path problem can be formulated as follows: given a collection B of polyhedral obstacles in R d , and source and target points s; t 2 R d , find a shortest obstacle-avoiding ...