Essential constraints of edge-constrained proximity graphs

DOI10.1007/978-3-319-44543-4_5MaRDI QIDQ5890863zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Jean-Lou De Carufel, Alina Shaikhet, Michiel Smid

Publication date 29 September 2016

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

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

zbMATH Keywords

\(\beta\)-skeletonsconstraintsDelaunayMSTproximity graphsvisibility

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Given a plane forest $F=(V,E)$ of $|V|=n$ points, we find the minimum set $SsubseteqE$ of edges such that the edge-constrained minimum spanning tree over the set $V$ of vertices and the set $S$ of constraints contains $F$. We present an $O(nlogn)$-time algorithm that solves this problem. We generalize this to other proximity graphs in the constraint setting, such as the relative neighbourhood graph, Gabriel graph, $$-skeleton and Delaunay triangulation. We present an algorithm that identifies the minimum set $SsubseteqE$ of edges of a given plane graph $I=(V,E)$ such that $$ for $$, where $$ is the constraint $$-skeleton over the set $V$ of vertices and the set $S$ of constraints. The running time of our algorithm is $O(n)$, provided that the constrained Delaunay triangulation of $I$ is given.

Recommendations

• Essential Constraints of Edge-Constrained Proximity Graphs
• scientific article; zbMATH DE number 1830717
• Optimal and suboptimal robust algorithms for proximity graphs
• Constrained generalized Delaunay graphs are plane spanners
• Constrained Delaunay triangulations

Cites work

• Constrained Delaunay triangulations
• Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
• Generalized Delaunay triangulation for planar graphs
• MINIMAL SET OF CONSTRAINTS FOR 2D CONSTRAINED DELAUNAY RECONSTRUCTION
• The relative neighbourhood graph of a finite planar set

Cited in

(1)

• Essential Constraints of Edge-Constrained Proximity Graphs

This page was built for publication: Essential constraints of edge-constrained proximity graphs

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