1985 · 225 citations · 6 references
Natural SciencesMathematicsOcean EngineeringComputational GeometryGeometrySpatial AnalysisConvex GeometryMetric GeometryVoronoi DiagramsConvex FunctionsDistance MeasuresVoronoi CellsVoronoi PolygonsWave Fronts
We present an “expanding waves” view of Voronoi diagrams that allows such diagrams to be defined for very general metrics and for distance measures that do not qualify as metrics. If a pebble is dropped into a still pond, circular waves move out from the point of impact. If n pebbles are dropped simultaneously, the places where wave fronts meet define the Voronoi diagram on the n points of impact.
6
Michael Ian Shamos, Dan Hoey · 1975 · 1.1K citations
On k-Nearest Neighbor Voronoi Diagrams in the Plane
Der-Tsai Lee · IEEE Transactions on Computers · 1982 · 323 citations
Efficient computation of continuous skeletons
David Kirkpatrick · 1979 · 255 citations
Colm Ó'Dúnlaing, Micha Sharir, Chee Yap · 1983 · 145 citations