Abstract
Two new algorithms finding relative neighborhood graph RNG(V) for a set V of n points are presented. The first algorithm solves this problem for input points in (R2,Lp) metric space in time O{n α(n,n)) if the Delaunay triangulation DT(V) is given. This time performance is achieved due to attractive and natural application of FIND-UNION data structure to represent so-called elimination forest of edges in DT(V). The second algorithm solves the relative neighborhood graph problem in (Rd,Lp), 1<p<∞, metric space in time O(n2) when no three points in V form an isosceles triangle. The complexity analysis of this algorithm is based on some general facts pertaining to properties of equilateral triangles in the metric space (Rd,Lp).
Original language | English |
---|---|
Title of host publication | Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 |
Editors | D. Soule |
Pages | 233-241 |
Number of pages | 9 |
ISBN (Electronic) | 0897912314, 9780897912310 |
DOIs | |
State | Published - Oct 1 1987 |
Event | 3rd Annual Symposium on Computational Geometry, SCG 1987 - Waterloo, Canada Duration: Jun 8 1987 → Jun 10 1987 |
Publication series
Name | Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987 |
---|
Conference
Conference | 3rd Annual Symposium on Computational Geometry, SCG 1987 |
---|---|
Country/Territory | Canada |
City | Waterloo |
Period | 6/8/87 → 6/10/87 |
Bibliographical note
Publisher Copyright:© 1987 ACM.
ASJC Scopus subject areas
- Geometry and Topology
- Computational Mathematics