Fitting Voronoi diagrams to planar tesselations

DOI10.1007/978-3-642-45278-9_30zbMATH Open1408.68141arXiv1308.5550OpenAlexW1839812710MaRDI QIDQ2870041FDOQ2870041

Authors: Greg Aloupis, Hebert Pérez-Rosés, Guillermo Pineda-Villavicencio, Perouz Taslakian, Dannier Trinchet-Almaguer 

Publication date: 17 January 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Given a tesselation of the plane, defined by a planar straight-line graph $G$, we want to find a minimal set $S$ of points in the plane, such that the Voronoi diagram associated with $S$ "fits" $G$. This is the Generalized Inverse Voronoi Problem (GIVP), defined in cite{Trin07} and rediscovered recently in cite{Baner12}. Here we give an algorithm that solves this problem with a number of points that is linear in the size of $G$, assuming that the smallest angle in $G$ is constant.

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

Recommendations

• On the Construction of Generalized Voronoi Inverse of a Rectangular Tessellation
• APPROXIMATION OF A TESSELLATION OF THE PLANE BY A VORONOI DIAGRAM
• Recognizing Voronoi Diagrams with Linear Programming
• Delaunay and Voronoi tessellations and minimal simple cycles in triangular region and regular-3 undirected planar graphs
• The inverse Voronoi problem in graphs. I: Hardness

zbMATH Keywords

Voronoi diagramDirichlet tesselationinverse Voronoi problemplanar tesselation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial aspects of tessellation and tiling problems (05B45)

Cited In (7)

• Minimal representations of tropical rational functions
• The inverse Voronoi problem in graphs. I: Hardness
• APPROXIMATION OF A TESSELLATION OF THE PLANE BY A VORONOI DIAGRAM
• Robustly computing restricted Voronoi diagrams (RVD) on thin-plate models
• Fitting spherical Laguerre Voronoi diagrams to real-world tessellations using planar photographic images
• Superposition of planar voronoi tessellations
• Title not available (Why is that?)

This page was built for publication: Fitting Voronoi diagrams to planar tesselations

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