Output-sensitive algorithm for computing -skeletons

DOI10.1007/S006070070013MaRDI QIDQ1840767zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 2 September 2001

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s006070070013

zbMATH Keywords

\(\beta\)-skeletonalgorithmscomputational geometryperformanceplanar set of points

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Review text

A \(\beta\)-skeleton of a planar set of \(n\) points, i.e. the geometric graph obtained by joining the pair of points whose \(\beta\)-neighborhood is empty, can be computed by a standard algorithm in time \(O(n^{5/2}\log n)\). An algorithm is proposed to detect the \(\beta\)-skeleton in time \(O(n\log n+k)\), where \(k\) is the size of the output graph. After the algorithm description, it is proved a theorem concerning the space and time necessary to perform the algorithm.

Recommendations

• Fast algorithms for computing -skeletons and their relatives.
• -skeletons for a set of line segments in R^2
• New sequential and parallel algorithms for computing the -spectrum
• New sequential and parallel algorithms for computing the \(\beta\)-spectrum
• Optimal and suboptimal robust algorithms for proximity graphs

Cited in

(6)

• New sequential and parallel algorithms for computing the \(\beta\)-spectrum
• New sequential and parallel algorithms for computing the -spectrum
• -skeletons for a set of line segments in R^2
• scientific article; zbMATH DE number 1830717 (Why is no real title available?)
• How \({\beta}\)-skeletons lose their edges
• Fast algorithms for computing -skeletons and their relatives.

This page was built for publication: Output-sensitive algorithm for computing \(\beta\)-skeletons

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