Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics. (English) Zbl 0486.68063


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Toussaint, G. T., The relative neighborhood graph of a finite planar set, Pattern Recognition, 12, 261-268 (1980) · Zbl 0437.05050
[2] Toussaint, G. T., Pattern recognition and geometrical complexity, (Proc. 5th Int. Conf. on Pattern Recognition. Proc. 5th Int. Conf. on Pattern Recognition, Miami Beach, U.S.A. (1980)), 1324-1327
[3] Toussaint, G. T., Computational geometric problems in pattern recognition, (Technical Report No. SOCS-81.12 (1981), McGill University) · Zbl 0223.68020
[4] Lankford, P. M., Regionalization: theory and alternative algorithms, Geog. Anal., 5, 133-144 (1973)
[5] Bentley, J. L.; Maurer, H. A., Efficient worst-case data structures for range searching, Acta Informatica, 13, 155-168 (1980) · Zbl 0423.68029
[6] Dobkin, D.; Lipton, R. J., Multidimensional search problems, SIAM J. Comput., 5, 181-186 (1976) · Zbl 0333.68031
[7] Bentley, J. L.; Friedman, J. H., Data structures for range searching, Computing Surveys, 11, 397-409 (1979)
[8] Bentley, J. L., Multidimensional divide-and-conquer, Commun. Ass. Comput. Mach., 23, 214-229 (1980) · Zbl 0434.68049
[9] Coppersmith, D.; Lee, D. T.; Wong, C. K., An elementary proof of nonexistence of isometries between \(L_p^{k\) · Zbl 0424.68026
[10] Shamos, M. I.; Hoey, D., Closest point problems, (Proc. 16th Ann. Symp. on the Foundations of Computer Science. Proc. 16th Ann. Symp. on the Foundations of Computer Science, IEEE (1975)), 151-162
[11] Shamos, M. I., Computational geometry, (PhD Dissertation (1978), Yale University) · Zbl 0759.68037
[12] Lee, D. T.; Wong, C. K., Voronoi diagrams in \(L_1 (L_∞)\) metrics with 2-dimensional storage applications, SIAM J. Comput., 9, 200-211 (1980) · Zbl 0447.68111
[13] Lee, D. T., Two-dimensional Voronoi diagrams in the \(L_p\)-metric, J. Ass. Comput. Mach., 27, 604-618 (1980) · Zbl 0445.68053
[14] Supowit, K., The relative neighborhood graph with an application to minimum spanning trees, (Computer Science Technical Report (1980), University of Illinois) · Zbl 0625.68047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.