The furthest-site geodesic Voronoi diagram
type: Item
instance of: scholarly article
title: The furthest-site geodesic Voronoi diagram
zbMATH Open document ID: 0770.68108
DOI: 10.1007/BF02189321
author: Boris Aronov
author: Steven Fortune
author: Gordon Wilfong
published in: Discrete \& Computational Geometry
publication date: 1993-05-16T00:00:00Z
full work available at URL: https://eudml.org/doc/131246
review text: The authors give a time and space efficient algorithm for computing the furthest-site Voronoi diagram of \(k\) point sites with respect to the geodesic metric within a simple \(n\)-sided polygon. This algorithm consists of two steps. First the restriction of the Voronoi diagram to the boundary of the polygon and then the extension of the diagram to the interior of the polygon is computed. The first step is much more involved. The authors use and refine a method developed by S. Suri.
reviewed by: Hans-Dietrich Hecker
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 52A37
zbMATH DE Number: 165213
zbMATH Keywords: Voronoi diagram
zbMATH Keywords: geodesic metric
MaRDI profile type: Publication
cites work: On the geodesic Voronoi diagram of point sites in a simple polygon
cites work: Q3787491
cites work: Algorithms for Reporting and Counting Geometric Intersections
cites work: Visibility and intersection problems in plane geometry
cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
cites work: Triangulating a simple polygon
cites work: Euclidean shortest paths in the presence of rectilinear barriers
cites work: Q3992847
cites work: Computing the geodesic center of a simple polygon
cites work: Computing geodesic furthest neighbors in simple polygons
description: scientific article; zbMATH DE number 165213