## 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^{2},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^{2}) 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 | |

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