𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fast algorithms for computing β-skeletons and their relatives

✍ Scribed by S.V. Rao; Asish Mukhopadhyay

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
191 KB
Volume
34
Category
Article
ISSN
0031-3203

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we present fast algorithms for computing -skeletons (Kirkpatrick and Radke, in: Toussaint (Ed.), Computational Geometry, North-Holland, Amsterdam, 1985, pp. 217}248) and two of its relatives, namely, k -skeletons, and additively weighted -skeletons. A -skeleton is a generalization of the Relative Neighborhood Graph, introduced by Toussaint (Toussaint, Pattern Recognition 12 (1980) 261}268). Our algorithms are in O(n log n) for *1 and in O(n log n) for 3[0, 1) under the metric ¸N for 1(p(R. In the ¸ and ¸ metrics our algorithms are in O(n log n). Given the Delaunay triangulation, the linear time algorithms known todate for computing -skeleton are restricted to the range 1) )2 under the metric ¸N for 1(p(R, provided "2 or p"2.

📜 SIMILAR VOLUMES

A Fast and Numerically Stable Euclidean-
A Fast and Numerically Stable Euclidean-like Algorithm for Detecting Relatively Prime Numerical Polynomials
✍ B. Beckermann; G. Labahn 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 644 KB

In this paper we provide a fast, numerically stable algorithm to determine when two given polynomials a and b are relatively prime and remain relatively prime even after small perturbations of their coefficients. Such a problem is important in many applications where input data are only available up

Enveloping triangulation method for dete
Enveloping triangulation method for detecting internal cavities in proteins and algorithm for computing their surface areas and volumes
✍ Ján Buša; Shura Hayryan; Chin-Kun Hu; Jaroslav Skřivánek; Ming-Chya Wu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 314 KB

## Abstract Detection and quantitative characterization of the internal cavities in proteins remain an important topic in studying protein structure and function. Here we propose a new analytical method for detecting the existence of cavities in proteins. The method is based on constructing the spe

A fast algorithm for a k-NN classifier b
A fast algorithm for a k-NN classifier based on the branch and bound method and computational quantity estimation
✍ Shin'ichiro Omachi; Hirotomo Aso 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 3 views

The nearest neighbor rule or k-nearest neighbor rule is a technique of nonparametric pattern recognition. Its algorithm is simple and the error is smaller than twice the Bayes error if there are enough training samples. However, it requires an enormous amount of computation, proportional to the numb