Farthest-point Voronoi diagrams in the presence of rectangular obstacles

03/07/2022
by   Mincheol Kim, et al.
0

We present an algorithm to compute the geodesic L_1 farthest-point Voronoi diagram of m point sites in the presence of n rectangular obstacles in the plane. It takes O(nm+n log n + mlog m) construction time using O(nm) space. This is the first optimal algorithm for constructing the farthest-point Voronoi diagram in the presence of obstacles. We can construct a data structure in the same construction time and space that answers a farthest-neighbor query in O(log(n+m)) time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset