ISSN:
1436-5057
Keywords:
AMS Subject Classifications: 11Y16, 65D18, 65U05, 65W40.
;
Key Words: Computational geometry, β-skeleton, shape of a point set, output-sensitive algorithm.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract The β-skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter β. For a fixed value of β, a β-skeleton is a geometric graph obtained by joining each pair of points whose β-neighborhood is empty. For β≥1, this neighborhood of a pair of points p i ,p j is the interior of the intersection of two circles of radius , centered at the points (1−β/2)p i +(β/2)p j and (β/2)p i +(1−β/2)p j , respectively. For β∈(0,1], it is the interior of the intersection of two circles of radius , passing through p i and p j . In this paper we present an output-sensitive algorithm for computing a β-skeleton in the metrics l 1 and l ∞ for any β≥2. This algorithm is in O(nlogn+k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n 5/2logn) [7].
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s006070070013
Permalink