On 2-site Voronoi diagrams under geometric distance functions

DOI10.1007/S11390-013-1328-2MaRDI QIDQ2434572zbMATH OpenOpenAlexFDO

Authors Gill Barequet, Matthew T. Dickerson, David Eppstein, David Hodorkovsky, Kira Vyatkina

Publication date 6 February 2014

Published in Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.4130

zbMATH Keywords

distance functionlower envelopeDavenport-Schinzel theorycrossing-number lemma

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We revisit a new type of a Voronoi diagram, in which distance is measured from a point to a pair of points. We consider a few more such distance functions, based on geometric primitives, and analyze the structure and complexity of the nearest- and furthest-neighbor Voronoi diagrams of a point set with respect to these distance functions.

Recommendations

• scientific article; zbMATH DE number 2185616
• 2-point site Voronoi diagrams
• On the Triangle-Perimeter Two-Site Voronoi Diagram
• scientific article; zbMATH DE number 1424293
• Voronoi diagrams and Delaunay triangulations

Cites work

• scientific article; zbMATH DE number 2185616 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1455125 (Why is no real title available?)
• Computational geometry. Algorithms and applications.
• Crossing-Free Subgraphs
• On a Problem of Heilbronn
• On the Triangle-Perimeter Two-Site Voronoi Diagram
• Voronoi diagrams with respect to criteria on vision information

Cited in

(8)

• On the Triangle-Perimeter Two-Site Voronoi Diagram
• The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites
• 2-point site Voronoi diagrams
• scientific article; zbMATH DE number 2185616 (Why is no real title available?)
• The limit of \(L_p\) Voronoi diagrams as \(p\rightarrow 0\) is the bounding-box-area Voronoi diagram
• On clustering induced Voronoi diagrams
• Round-trip Voronoi diagrams and doubling density in geographic networks
• scientific article; zbMATH DE number 1390217 (Why is no real title available?)

This page was built for publication: On 2-site Voronoi diagrams under geometric distance functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2434572)