An almost naive algorithm for finding relative neighbourhood graphs in L p metrics

Jyrki Katajainen; Olli Nevalainen

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1987)

  • Volume: 21, Issue: 2, page 199-215
  • ISSN: 0988-3754

How to cite

top

Katajainen, Jyrki, and 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 21.2 (1987): 199-215. <http://eudml.org/doc/92284>.

@article{Katajainen1987,
author = {Katajainen, Jyrki, Nevalainen, Olli},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {relative neighbourhood graph; metric; algorithm},
language = {eng},
number = {2},
pages = {199-215},
publisher = {EDP-Sciences},
title = {An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics},
url = {http://eudml.org/doc/92284},
volume = {21},
year = {1987},
}

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
PB - EDP-Sciences
VL - 21
IS - 2
SP - 199
EP - 215
LA - eng
KW - relative neighbourhood graph; metric; algorithm
UR - http://eudml.org/doc/92284
ER -

References

top
  1. 1. J. L. BENTLEY and H. A. MAURER, Efficient Worst-Case Data Structures for Range Searching, Acta Informatica, Vol. 13, 1980, pp. 155-168. Zbl0423.68029MR564462
  2. 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. Zbl0424.68026MR548491
  3. 3. P. FRANKL, Privite communication, May 23, 1985. 
  4. 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. 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. Zbl0196.02203MR256902
  6. 6. C. HYLTÉN-CAVALLIUS, On a Combinatorical Problem, Colloquium Mathematicum, Vol. 6, 1958, pp. 59-65. Zbl0086.01202MR103158
  7. 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. 8. J. KATAJAINEN and O. NEVALAINEN, Computing Relative Neighbourhood Graphs in the Plane, Pattern Recognition, Vol. 19, 1986, pp. 221-228. Zbl0602.68089
  9. 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). Zbl0653.68034MR896149
  10. 10. M. KOPPINEN, Privite communication, December 18, 1985. 
  11. 11. J. O'ROURKE, Computing the Relative Neighborhood Graph in the L1 and L∞ Metrics, Pattern Recognition, Vol. 15, 1982, pp. 189-192. Zbl0486.68063MR662775
  12. 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. Zbl0625.68047MR709827
  13. 13. G. T. TOUSSAINT, The Relative Neighbourhood Graph of a Finite Planar Set, Pattern Recognition, Vol. 12, 1980, pp. 261-268. Zbl0437.05050MR591314
  14. 14. G. T. TOUSSAINT, Comment on "Algorithms for Computing Relative Neighbourhood Graph", Electronics Letters, Vol. 16, 1980, pp. 860-861. MR592510
  15. 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. Zbl0467.90028
  16. 16. R. B. URQUHART, Algorithms for Computation of Relative Neighbourhood Graph, Electronics Letters, Vol. 16, 1980, pp. 556-557. MR578786
  17. 17. D. WOOD, An Isothetic View of Computational Geometry, Report CS-84-01, Computer Science Department, University of Waterloo, Canada, 1984. Zbl0614.68078MR834395
  18. 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. Zbl0492.68050MR677663

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.