-skeletons for a set of line segments in R^2

DOI10.1007/978-3-319-22177-9_6MaRDI QIDQ2947870zbMATH OpenOpenAlexFDO

Authors Mirosław Kowaluk, Gabriela Majewska

Publication date 29 September 2015

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: $$-skeletons are well-known neighborhood graphs for a set of points. We extend this notion to sets of line segments in the Euclidean plane and present algorithms computing such skeletons for the entire range of $$ values. The main reason of such extension is the possibility to study $$-skeletons for points moving along given line segments. We show that relations between $$-skeletons for $$, $1$-skeleton (Gabriel Graph), and the Delaunay triangulation for sets of points hold also for sets of segments. We present algorithms for computing circle-based and lune-based $$-skeletons. We describe an algorithm that for $$ computes the $$-skeleton for a set $S$ of $n$ segments in the Euclidean plane in $O(n^{2}alpha(n)logn)$ time in the circle-based case and in $O(n^{2}lambd{a}_4(n))$ in the lune-based one, where the construction relies on the Delaunay triangulation for $S$, $alpha$ is a functional inverse of Ackermann function and $lambd{a}_4(n)$ denotes the maximum possible length of a $(n,4)$ Davenport-Schinzel sequence. When $$, the $$-skeleton can be constructed in a $O(n^{3}lambd{a}_4(n))$ time. In the special case of $$, which is a generalization of Gabriel Graph, the construction can be carried out in a $O(nlogn)$ time.

Recommendations

• Fast algorithms for computing -skeletons and their relatives.
• Output-sensitive algorithm for computing -skeletons
• How \({\beta}\)-skeletons lose their edges
• New sequential and parallel algorithms for computing the -spectrum
• New sequential and parallel algorithms for computing the \(\beta\)-spectrum

Cites work

• A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
• Beta-skeletons have unbounded dilation
• Finding the upper envelope of n line segments in O(n log n) time
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• Optimal and suboptimal robust algorithms for proximity graphs
• Straight skeletons for general polygonal figures in the plane
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• The relative neighbourhood graph of a finite planar set
• Triangulations of Line Segment Sets in the Plane

Cited in

(7)

• Output-sensitive algorithm for computing -skeletons
• New sequential and parallel algorithms for computing the \(\beta\)-spectrum
• New sequential and parallel algorithms for computing the -spectrum
• scientific article; zbMATH DE number 2086250 (Why is no real title available?)
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• How \({\beta}\)-skeletons lose their edges
• Fast algorithms for computing -skeletons and their relatives.

This page was built for publication: \(\beta\)-skeletons for a set of line segments in \(\mathbb R^2\)

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