Elliptic Gabriel graph for finding neighbors in a point set and its application to normal vector estimation
| Autor: | Hayong Shin, Byoung K. Choi, Joon C. Park |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Discrete mathematics
Relative neighborhood graph Gabriel graph Strength of a graph Computer Graphics and Computer-Aided Design Industrial and Manufacturing Engineering Computer Science Applications law.invention Planar graph Combinatorics symbols.namesake law Line graph symbols Null graph Lattice graph Mathematics Distance-hereditary graph |
| Zdroj: | Computer-Aided Design. 38:619-626 |
| ISSN: | 0010-4485 |
| DOI: | 10.1016/j.cad.2006.02.008 |
| Popis: | Point-based shape representation has received increased attention in recent years, mainly due to its simplicity. One of the most fundamental operations for point set processing is to find the neighbors of each point. Mesh structures and neighborhood graphs are commonly used for this purpose. However, though meshes are very popular in the field of computer graphics, neighbor relations encoded in a mesh are often distorted. Likewise, neighborhood graphs, such as the minimum spanning tree (MST), relative neighborhood graph (RNG), and Gabriel graph (GG), are also imperfect as they usually give too few neighbors for a given point. In this paper, we introduce a generalization of Gabriel graph, named elliptic Gabriel graph (EGG), which takes an elliptic influence region instead of the circular region in GG. In order to determine the appropriate aspect ratio of the elliptic influence region of EGG, this paper also presents the analysis between the aspect ratio of the elliptic influence region and the average valence of the resulting neighborhood. Analytic and empirical test results are included. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect