01206663

j

01206663 Mitra, Pinaki Nandy, Subhas C. Efficient computation of rectilinear geodesic Voronoi neighbor in the presence of obstacles. J. Algorithms 28, No.2, 315-338 (1998). 1998 Elsevier, San Diego, CA EN geodesic Voronoi neighbor

doi:10.1006/jagm.1998.0939

Summary: This paper presents two simple algorithms for finding the rectilinear geodesic Voronoi neighbor (site) of an arbitrary query point $q$, where $n$ sites are located on a rectangular region among a set of $m$ isothetic obstacles. The first one works in $O(\log(m+ n))$ time, where the obstacles are vertical line segments. This requires a preprocessing step that takes $O((m+ n)\log(m+ n))$ time, using a layered segment tree data structure, and stores the preprocessed information in a data structure of size $O(m\log m+n)$. In the second algorithm, the obstacles may be isothetic rectangles, but the sites are located on the periphery of the bounding rectangle. This algorithm uses a planar graph, called the carrier graph, for preprocessing and solves teh geodesic Voronoi neighbor query in $O(\log(m+ n))$ time. The preprocessing time for this problem is $O((m+ n)\log(m+ n))$, and it consumes $O(m+ n)$ space.