A note on relative neighborhood graphs

Jerzy W. Jaromczyk; Miroslaw Kowaluk

doi:10.1145/41958.41983

A note on relative neighborhood graphs

Jerzy W. Jaromczyk, Miroslaw Kowaluk

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

33 Scopus citations

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 (R²,L_p) 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 (R^d,L_p), 1<p<∞, metric space in time O(n²) 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 (R^d,L_p).

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	https://doi.org/10.1145/41958.41983
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

Access to Document

10.1145/41958.41983

Cite this

@inproceedings{6d862e3412e24b778511e31e46ad39fd,

title = "A note on relative neighborhood graphs",

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), 12) 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).",

author = "Jaromczyk, {Jerzy W.} and Miroslaw Kowaluk",

note = "Publisher Copyright: {\textcopyright} 1987 ACM.; 3rd Annual Symposium on Computational Geometry, SCG 1987 ; Conference date: 08-06-1987 Through 10-06-1987",

year = "1987",

month = oct,

day = "1",

doi = "10.1145/41958.41983",

language = "English",

series = "Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987",

pages = "233--241",

editor = "D. Soule",

booktitle = "Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987",

}

Jaromczyk, JW & Kowaluk, M 1987, A note on relative neighborhood graphs. in D Soule (ed.), Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987. Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987, pp. 233-241, 3rd Annual Symposium on Computational Geometry, SCG 1987, Waterloo, Canada, 6/8/87. https://doi.org/10.1145/41958.41983

A note on relative neighborhood graphs. / Jaromczyk, Jerzy W.; Kowaluk, Miroslaw.
Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987. ed. / D. Soule. 1987. p. 233-241 (Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A note on relative neighborhood graphs

AU - Jaromczyk, Jerzy W.

AU - Kowaluk, Miroslaw

PY - 1987/10/1

Y1 - 1987/10/1

N2 - 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), 12) 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).

AB - 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), 12) 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).

UR - http://www.scopus.com/inward/record.url?scp=84984881052&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84984881052&partnerID=8YFLogxK

U2 - 10.1145/41958.41983

DO - 10.1145/41958.41983

M3 - Conference contribution

AN - SCOPUS:84984881052

T3 - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987

SP - 233

EP - 241

BT - Proceedings of the 3rd Annual Symposium on Computational Geometry, SCG 1987

A2 - Soule, D.

T2 - 3rd Annual Symposium on Computational Geometry, SCG 1987

Y2 - 8 June 1987 through 10 June 1987

ER -

A note on relative neighborhood graphs

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this