Paper Info
Title
An efficient algorithm for three-dimensional beta-complex and beta-shape via a quasi-triangulation
Abstract
The concept of a β-shape has been recently proposed by extending the concept of the well-known α-shape. Since the β-shape takes full consideration of the Euclidean geometry of spherical particles, it is better suited than the (weighted) α-shape for applications using spatial queries on the system of variable sized spheres based on the Euclidean distance metric. In this paper, we present an efficient and elegant algorithm which computers a β-shape from a quasi-triangulation in O(log m + k) time in the worst case, where the quasi-triangulation has m simplicies and the boundary of β-shape consists of k simplicies. We believe that the β-shape and β-complex for a set of variable sized spheres (such as the atoms in a protein) will be very useful in the near future since the precise and efficient analysis of molecular structure can be conveniently facilitated by using these structures.
Year
DOI
Venue
2007
10.1145/1236246.1236292
Symposium on Solid and Physical Modeling
Keywords
DocType
Citations 
voronoi diagram of spheres,complex,α-complex,β-complex,β-shape,α-shape,quasi-triangulation
Conference
2
PageRank 
References 
Authors
0.39
11
4
Name
Order
Citations
PageRank
Jeongyeon Seo1353.60
Youngsong Cho225022.15
Donguk Kim329626.68
Deok-Soo Kim463359.12