Paper Info
Title
Trash removal algorithm for fast construction of the elliptic Gabriel graph using Delaunay triangulation
Abstract
Given a set of points P, finding near neighbors among the points is an important problem in many applications in CAD/CAM, computer graphics, computational geometry, etc. In this paper, we propose an efficient algorithm for constructing the elliptic Gabriel graph (EGG), which is a generalization of the well-known Gabriel graph and parameterized by a non-negative value @a. Our algorithm is based on the observation that a candidate point which may define an edge of an EGG with a given point p@?P is always in the scaled Voronoi region of p with a scale factor 2/@a^2 when the parameter @a=1, due to the fact that EGG is a subgraph of the Delaunay graph of P, EGG can be efficiently computed by watching the validity of each edge in the Delaunay graph. The proposed algorithm is shown to have its time complexity as O(n^3) in the worst case and O(n) in the average case when @a is moderately close to unity. The idea presented in this paper may similarly apply to other problems for the proximity search for point sets.
Year
DOI
Venue
2008
10.1016/j.cad.2008.05.002
Computer-Aided Design
Keywords
Field
DocType
points p,delaunay triangulation,delaunay graph,trash removal algorithm,fast construction,proposed algorithm,elliptic gabriel graph,efficient algorithm,point p,neighborhood graph,search space reduction,candidate point,point set,average case,voronoi diagram,well-known gabriel graph,computational geometry,computer graphic,search space,time complexity
Geometric graph theory,Discrete mathematics,Combinatorics,Bowyer–Watson algorithm,Beta skeleton,Line graph,Gabriel graph,Graph factorization,Algorithm,Butterfly graph,Mathematics,Pitteway triangulation
Journal
Volume
Issue
ISSN
40
8
Computer-Aided Design
Citations 
PageRank 
References 
1
0.36
14
Authors
4
Name
Order
Citations
PageRank
Changhee Lee1196.81
Donguk Kim229626.68
Hayong Shin312617.25
Deok-Soo Kim463359.12