Farthest-point Voronoi diagrams in the presence of rectangular obstacles

03/07/2022

∙

by   Mincheol Kim, et al.

∙

0

∙

share

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.