An almost naive algorithm for finding relative neighbourhood graphs in L p metrics
Katajainen, Jyrki ; Nevalainen, Olli
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987), p. 199-215 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1987-01-01
@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},
     volume = {21},
     year = {1987},
     pages = {199-215},
     mrnumber = {894711},
     zbl = {0634.68030},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 199-215. http://gdmltest.u-ga.fr/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 564462 | Zbl 0423.68029

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 548491 | Zbl 0424.68026

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 256902 | Zbl 0196.02203

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

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 0602.68089

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 896149 | Zbl 0653.68034

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 662775 | Zbl 0486.68063

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 709827 | Zbl 0625.68047

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

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

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 0467.90028

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

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

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 677663 | Zbl 0492.68050