×

zbMATH — the first resource for mathematics

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

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[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, (), 1324-1327
[3] Toussaint, G.T., Computational geometric problems in pattern recognition, () · 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 Lpk and lqk, IBM J. res. dev., 23, 696-699, (1979) · Zbl 0424.68026
[10] Shamos, M.I.; Hoey, D., Closest point problems, (), 151-162
[11] Shamos, M.I., Computational geometry, () · Zbl 0759.68037
[12] Lee, D.T.; Wong, C.K., Voronoi diagrams in L1 (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 Lp-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, () · 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.