Output-Sensitive Algorithm for Computing β-Skeletons |
| |
Authors: | A Mukhopadhyay S V Rao |
| |
Affiliation: | (1) School of Computer Science University of Windsor Windsor, ON N9B 3P4 Canada e-mail: asishm@cs.uwindsor.ca, CA;(2) Department of Computer Science and Engineering Indian Institute of Technology, Guwahati Guwahati – 781 001, Assam India e-mail: svrao@iitg.ernet.in, IN |
| |
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].
Received April 26, 2000 |
| |
Keywords: | AMS Subject Classifications: 11Y16 65D18 65U05 65W40 |
本文献已被 SpringerLink 等数据库收录! |
|