Constructing the relative neighborhood graph in 3-dimensional Euclidean space

Jerzy W. Jaromczyk; Mirosław Kowaluk

doi:10.1016/0166-218X(91)90069-9

Constructing the relative neighborhood graph in 3-dimensional Euclidean space

Jerzy W. Jaromczyk, Mirosław Kowaluk

Computer Science

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

Abstract

The relative neighborhood graph for a finite set S={p₁,...,p_N} of points, briefly RNG(S), is defined by the following formation rule: p_ip_j is an edge in RNG(S) if and only if for all p_kε{lunate}S-{p_i, p_j}, dist(p_i, p_j)≤max(dist(p_i,p_k), dist(p_j,p_k)). We show that RNG for point sets in R³ can be constructed in optimal space and O(N²log N) time. Also, combinatorial estimates on the size of RNG in R³ are given.

Original language	English
Pages (from-to)	181-191
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	31
Issue number	2
DOIs	https://doi.org/10.1016/0166-218X(91)90069-9
State	Published - Apr 15 1991

Bibliographical note

Funding Information:
* The work on this paper has been partially supported by the Research Committee Grant of the University of Kentucky and a grant from the Center for Robotics and Manufacturing Systems, University of Kentucky.

Funding

* The work on this paper has been partially supported by the Research Committee Grant of the University of Kentucky and a grant from the Center for Robotics and Manufacturing Systems, University of Kentucky.

Funders	Funder number
Center for Robotics and Manufacturing Systems, University of Kentucky
University of Kentucky

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/0166-218X(91)90069-9

Cite this

@article{7802db5d89b449f99d040cd21b109aba,

title = "Constructing the relative neighborhood graph in 3-dimensional Euclidean space",

abstract = "The relative neighborhood graph for a finite set S=\{p1,...,pN\} of points, briefly RNG(S), is defined by the following formation rule: pipj is an edge in RNG(S) if and only if for all pkε\{lunate\}S-\{pi, pj\}, dist(pi, pj)≤max(dist(pi,pk), dist(pj,pk)). We show that RNG for point sets in R3 can be constructed in optimal space and O(N2log N) time. Also, combinatorial estimates on the size of RNG in R3 are given.",

author = "Jaromczyk, \{Jerzy W.\} and Miros{\l}aw Kowaluk",

note = "Funding Information: * The work on this paper has been partially supported by the Research Committee Grant of the University of Kentucky and a grant from the Center for Robotics and Manufacturing Systems, University of Kentucky.",

year = "1991",

month = apr,

day = "15",

doi = "10.1016/0166-218X(91)90069-9",

language = "English",

volume = "31",

pages = "181--191",

number = "2",

}

TY - JOUR

T1 - Constructing the relative neighborhood graph in 3-dimensional Euclidean space

AU - Jaromczyk, Jerzy W.

AU - Kowaluk, Mirosław

N1 - Funding Information: * The work on this paper has been partially supported by the Research Committee Grant of the University of Kentucky and a grant from the Center for Robotics and Manufacturing Systems, University of Kentucky.

PY - 1991/4/15

Y1 - 1991/4/15

N2 - The relative neighborhood graph for a finite set S={p1,...,pN} of points, briefly RNG(S), is defined by the following formation rule: pipj is an edge in RNG(S) if and only if for all pkε{lunate}S-{pi, pj}, dist(pi, pj)≤max(dist(pi,pk), dist(pj,pk)). We show that RNG for point sets in R3 can be constructed in optimal space and O(N2log N) time. Also, combinatorial estimates on the size of RNG in R3 are given.

AB - The relative neighborhood graph for a finite set S={p1,...,pN} of points, briefly RNG(S), is defined by the following formation rule: pipj is an edge in RNG(S) if and only if for all pkε{lunate}S-{pi, pj}, dist(pi, pj)≤max(dist(pi,pk), dist(pj,pk)). We show that RNG for point sets in R3 can be constructed in optimal space and O(N2log N) time. Also, combinatorial estimates on the size of RNG in R3 are given.

UR - https://www.scopus.com/pages/publications/0003611765

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

U2 - 10.1016/0166-218X(91)90069-9

DO - 10.1016/0166-218X(91)90069-9

M3 - Article

AN - SCOPUS:0003611765

SN - 0166-218X

VL - 31

SP - 181

EP - 191

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

ER -

Constructing the relative neighborhood graph in 3-dimensional Euclidean space

Abstract

Bibliographical note

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this