An almost naive algorithm for finding relative neighbourhood graphs in L p metrics
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987) no. 2, pp. 199-215. 
@article{ITA_1987__21_2_199_0,
     author = {Katajainen, Jyrki and Nevalainen, Olli},
     title = {An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {199--215},
     publisher = {EDP-Sciences},
     volume = {21},
     number = {2},
     year = {1987},
     mrnumber = {894711},
     zbl = {0634.68030},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1987__21_2_199_0/}
}
TY  - JOUR
AU  - Katajainen, Jyrki
AU  - Nevalainen, Olli
TI  - An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1987
SP  - 199
EP  - 215
VL  - 21
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1987__21_2_199_0/
LA  - en
ID  - ITA_1987__21_2_199_0
ER  - 
%0 Journal Article
%A Katajainen, Jyrki
%A Nevalainen, Olli
%T An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1987
%P 199-215
%V 21
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1987__21_2_199_0/
%G en
%F ITA_1987__21_2_199_0
Katajainen, Jyrki; Nevalainen, Olli. An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987) no. 2, pp. 199-215. http://archive.numdam.org/item/ITA_1987__21_2_199_0/

1. J. L. Bentley and H. A. Maurer, Efficient Worst-Case Data Structures for Range Searching, Acta Informatica, Vol. 13, 1980, pp. 155-168. | MR | Zbl

2. D. Coppersmith, D. T. Lee and C. K. Wong, An Elementary Proof of Nonexistence of Isometries Between lkp and lkq, I.B.M. Journal of Research and Development, Vol. 23, 1979, pp. 696-699. | MR | Zbl

3. P. Frankl, Privite communication, May 23, 1985.

4. H. N. Gabow, J. L. Bentley and R. E. Tarjan, Scaling and Related Techniques for Geometry Problems, in Proc. 16th Annual A.C.M. Symposium on Theory of Computing, Washington D.C., 1984, pp. 135-143.

5. R. K. Guy, and S. Znám, A Problem of Zarankiewicz, in Recent Progress in Combinatorics, W. T. TUTTE Ed., Academic Press, 1969, pp. 237-243. | MR | Zbl

6. C. Hyltén-Cavallius, On a Combinatorical Problem, Colloquium Mathematicum, Vol. 6, 1958, pp. 59-65. | MR | Zbl

7. J. Katajainen and M. Koppinen, A note on Systems of Finite Sets Satisfying an Intersection Condition, Report B36, Department of Computer Science, University of Turku, Finland, 1985.

8. J. Katajainen and O. Nevalainen, Computing Relative Neighbourhood Graphs in the Plane, Pattern Recognition, Vol. 19, 1986, pp. 221-228. | Zbl

9. J. Katajainen, O. Nevalainen and J. Teuhola, A Linear Expected-Time Algorithm for Computing Planar Relative Neighbourhood Graphs, in Information Processing Letters (to appear). | MR | Zbl

10. M. Koppinen, Privite communication, December 18, 1985.

11. J. O'Rourke, Computing the Relative Neighborhood Graph in the L1 and L∞ Metrics, Pattern Recognition, Vol. 15, 1982, pp. 189-192. | MR | Zbl

12. K. J. Supowit, The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, Journal of the A.C.M., Vol. 30, 1983, pp. 428-448. | MR | Zbl

13. G. T. Toussaint, The Relative Neighbourhood Graph of a Finite Planar Set, Pattern Recognition, Vol. 12, 1980, pp. 261-268. | MR | Zbl

14. G. T. Toussaint, Comment on "Algorithms for Computing Relative Neighbourhood Graph", Electronics Letters, Vol. 16, 1980, pp. 860-861. | MR

15. G. T. Toussaint and R. Menard, Fast Algorithms for Computing the Planar Relative Neighborhood Graph, in Proc. 5th Symposium on Operations Research, Köln, F.R. Germany, 1980, pp. 425-428. | Zbl

16. R. B. Urquhart, Algorithms for Computation of Relative Neighbourhood Graph, Electronics Letters, Vol. 16, 1980, pp. 556-557. | MR

17. D. Wood, An Isothetic View of Computational Geometry, Report CS-84-01, Computer Science Department, University of Waterloo, Canada, 1984. | MR

18. A. C. Yao, On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems, S.I.A.M. Journal of Computing, Vol. 11, 1982, pp. 721-736. | MR | Zbl