Some Studies on Beta-Skeletons

S. V. Rao, August, 1999

Supervisor: Prof. Asish Mukhopadhyay

The present thesis is a study of some algorithmic aspects of $ß$-skeletons. The concept of a $ß$-skeleton was introduced by Kirkpatrick and Radke[KR85] as a way of capturing the ``internal shape'' of a planar set of points. Indeed, we get an entire spectrum of shapes by varying the parameter $ß$. For a fixed value of ß, the ``internal shape'' is a geometric graph, obtained by joining each pair of points whose $ß$-neighborhood is empty.

For $ß\; >=\; 1$, the $ß$-neighborhood of a pair of points $p$_i,p_j is the interior of the intersection of two circles of radius ß dist(p_i,p_j) /2, centered at the points (1-ß/2)p_i+(ß/2)p_j and (ß/2)p_i+(1-ß/2)p_j, respectively. For ß in [0,1], it is the interior of the intersection of two circles of radius dist(p_i,p_j)/(2ß), passing through p_i and p_j. We denote this neighborhood by lune_ß(p_i,p_j). The parameter $ß$ characterizes the neighborliness of a pair of points.

Let P = {p₁,p₂,......,p_n} be a set of n points in the plane. The $ß$-skeleton of $P$ is a geometric graph $(P,E)$ such that for every $p$_i,p_j in P, the edge $p$_i p_j in E if and only if the $ß-lune\; lune$_ß(p_i,p_j) is empty.

We discuss a sweepline algorithm for constructing a $ß$-skeleton for any $ß\; >=\; 0$. The time-complexity of our algorithm is in O(n^3/2 log n) for $ß\; >=\; 1$ and in $O(n5/2log\; n)$, for $ß\; in\; [0,1)$ under the metric $L$_p for . In the metrics $L$₁ and $L$ _infinite, our algorithm takes $O(n5/2log\; n)$ time for any $ß\; >=\; 0$.

The concept of a ß-skeleton have natural generalizations to that of kß-skeletons and additively weighted ß-skeletons. We have shown that the above sweepline method can be extended to construct these geometric graphs too. The time complexity of computing the kß-skeleton is in $O(k\; n3/2log\; n\; +\; k2n)$ for ß >= 1 and in $O(n5/2log\; n\; +\; n2k)$ for ß in the range [0, 1). The time complexity of computing the weighted ß-skeleton is in $O(n3/2log\; n)$ for ß >= 1 and in $O(n5/2log\; n)$ for ß in the range [0, 1).

We have obtained an optimal output-sensitive algorithm for computing a ß-skeleton for any ß >= 2 in metric $L$₁ and L_infinite. The time complexity is in O(n log n + k), where k is the size of the ß-skeleton.

We have presented efficient algorithms for computing the entire spectrum of ß-shapes in $L$₂ metric. This means computing for each pair of points the largest ß value, $ß$_max, for which the ß-neighborhood is empty. Our algorithms are in $O(n3/2log\; n\; +\; K)$ for $ß$_max values not less than 1 and in $O(n2log\; n\; +\; K)$ time for values greater than or equal to 0. A point that lies in the ß-neighborhood of an edge is a witness to this edge. The quantity K is a count of the number of times that the edges of the initial graph on P are witnessed for ß = infinite. We have also presented algorithms for computing the spectra of of kß-shapes and additively-weighted ß-shapes.

We have extend the definition of ß-skeleton into higher-dimensions. We have shown that the size of the ß-skeleton for ß > 2 is linear in d-dimensional space, for any fixed d. We have presented an efficient algorithm for computing the ß-skeletons for ß > 2.

Full Thesis (PS-gzipped 213K)

Back to PhD theses list

Feedback: webmaster@cse.iitk.ac.in