{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:14:05Z","timestamp":1777518845215,"version":"3.51.4"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1980,6,1]],"date-time":"1980-06-01T00:00:00Z","timestamp":328665600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["International Journal of Computer and Information Sciences"],"published-print":{"date-parts":[[1980,6]]},"DOI":"10.1007\/bf00977785","type":"journal-article","created":{"date-parts":[[2005,1,14]],"date-time":"2005-01-14T15:49:06Z","timestamp":1105717746000},"page":"219-242","source":"Crossref","is-referenced-by-count":1192,"title":["Two algorithms for constructing a Delaunay triangulation"],"prefix":"10.1007","volume":"9","author":[{"given":"D. T.","family":"Lee","sequence":"first","affiliation":[]},{"given":"B. J.","family":"Schachter","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"CR1","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1111\/j.2517-6161.1974.tb00999.x","volume":"36","author":"J. Besag","year":"1974","unstructured":"J. Besag, ?Spatial interaction and the statistical analysis of lattice systems,?J. Royal Stat. Soc. B 36 (2):192?236 (1974).","journal-title":"J. Royal Stat. Soc. B"},{"key":"CR2","volume-title":"University of Michigan Contributions of the Institute of Human Adjustment Social Science","author":"D. J. Bogue","year":"1949","unstructured":"D. J. Bogue, ?The Structure of the Metropolitan Community,? University of Michigan Contributions of the Institute of Human Adjustment Social Science, University of Michigan, Ann Arbor, Michigan (1949)."},{"key":"CR3","unstructured":"B. Delaunay, ?Sur la sph\u00e8re vide,?Bull. Acad. Science USSR VII:Class. Sci. Mat. Nat. 793?800 (1934)."},{"key":"CR4","unstructured":"H. Fuchs and Z. M. Kedem, ?The Highly Intelligent Tablet as an Efficient Printing Device for Interactive Graphics,? University of Texas (Dallas) (1979). Program in Math. Science (1979)."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(78)90062-5","volume":"7","author":"M. R. Garey","year":"1978","unstructured":"M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, ?Triangulating a simple polygon,?Inform. Proc. Letters 7:175?179 (June 1978).","journal-title":"Inform. Proc. Letters"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1214\/aoms\/1177704464","volume":"33","author":"E. N. Gilbert","year":"1962","unstructured":"E. N. Gilbert, ?Random subdivision of space into crystals,?Ann. Math. Stat. 33: 958?972 (1962).","journal-title":"Ann. Math. Stat."},{"issue":"2","key":"CR7","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1093\/comjnl\/21.2.168","volume":"21","author":"P. J. Green","year":"1978","unstructured":"P. J. Green and R. Sibson, ?Computing Dirichlet tesselations in the plane,?Computer J. 21 (2):168?173 (July 1978).","journal-title":"Computer J."},{"key":"CR8","first-page":"433","volume":"64","author":"T. Kiang","year":"1966","unstructured":"T.Kiang, ?Random fragmentation in two and three dimensions,?Z. Astrophysik 64:433?439 (1966).","journal-title":"Z. Astrophysik"},{"key":"CR9","volume-title":"Generation of a Triangular Grid with Applications to Contour Plotting","author":"C. L. Lawson","year":"1972","unstructured":"C. L. Lawson, ?Generation of a Triangular Grid with Applications to Contour Plotting,? Technical Memo. 299, Jet Propulsion Laboratory, Pasadena, California (February 1972)."},{"key":"CR10","volume-title":"in Mathematical Software III","author":"C. L. Lawson","year":"1977","unstructured":"C. L. Lawson, ?Software forC 1 surface interpolation,?in Mathematical Software III, J. Rice, Ed. (Academic Press, New York, 1977)."},{"key":"CR11","series-title":"Technical Report Eng.","volume-title":"On Finding ?-Nearest Neighbors in the Plane","author":"D. T. Lee","year":"1976","unstructured":"D. T. Lee, ?On Finding ?-Nearest Neighbors in the Plane,? Technical Report Eng. 76-2216, Coordinated Science Laboratory, University of Illinois, Urbana, Illinois (1976)."},{"key":"CR12","series-title":"Coordinated Science Laboratory Report ACT-12","volume-title":"Ph.D. Thesis","author":"D. T. Lee","year":"1978","unstructured":"D. T. Lee, ?Proximity and Reachability in the Plane,? Ph.D. Thesis, Coordinated Science Laboratory Report ACT-12, University of Illinois, Urbana, Illinois (1978)."},{"key":"CR13","unstructured":"D. T. Lee, ?Two-dimensional Voronoi diagrams in theL p-metric,?J. ACM (accepted for publication)."},{"key":"CR14","unstructured":"D. T. Lee and C. K. Wong, ?Voronoi diagrams inL 1 (L ?) metrics with two-dimensional storage applications,?SIAM J. Computing (accepted for publication)."},{"issue":"4","key":"CR15","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1093\/comjnl\/21.4.324","volume":"21","author":"B. A. Lewis","year":"1978","unstructured":"B. A. Lewis and J. S. Robinson, ?Triangulation of planar regions with applications,?Computer J. 21 (4):324?332 (Nov. 1978).","journal-title":"Computer J."},{"key":"CR16","series-title":"Technical Report MIT\/LCS\/TM-88","volume-title":"On Triangulation of a Set of Points in the Plane","author":"E. L. Lloyd","year":"1977","unstructured":"E. L. Lloyd, ?On Triangulation of a Set of Points in the Plane,? Technical Report MIT\/LCS\/TM-88, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts (May 1977)."},{"key":"CR17","volume-title":"Location in Space: A Theoretical Approach to Economic Geography","author":"P. E. Lloyd","year":"1972","unstructured":"P. E. Lloyd and P. Dicken,Location in Space: A Theoretical Approach to Economic Geography (Harper and Row, New York, 1972)."},{"issue":"5","key":"CR18","first-page":"1","volume":"36","author":"B. Matern","year":"1960","unstructured":"B. Matern, ?Spatial variation,?Medd. Statens Skogsforskninginstit. 36 (5):1?144 (1960).","journal-title":"Medd. Statens Skogsforskninginstit."},{"issue":"2","key":"CR19","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1093\/comjnl\/19.2.178","volume":"19","author":"D. H. McLain","year":"1976","unstructured":"D. H. McLain, ?Two dimensional interpolation from random data,?Computer J. 19 (2):178?181 (1976); Errata,Computer J. 19 (4):384 (1976).","journal-title":"Computer J."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/1011071","volume":"11","author":"R. E. Miles","year":"1969","unstructured":"R. E. Miles, ?Solution to problem 67-15 (Probability distribution of a network of triangles),?SIAM Rev. 11:399?402 (1969).","journal-title":"SIAM Rev."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0025-5564(70)90061-1","volume":"6","author":"R. E. Miles","year":"1970","unstructured":"R. E. Miles, ?On the homogeneous planar Poisson point-process,?Math. Biosciences 6:85?127 (1970).","journal-title":"Math. Biosciences"},{"issue":"1?2","key":"CR22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF01896082","volume":"31","author":"J. Molnar","year":"1978","unstructured":"J. Molnar, ?Packing of congruent spheres in a strip,?Acta Math. Acad. Sciences Hungaricae Jomus 31 (1?2):173?183 (1978).","journal-title":"Acta Math. Acad. Sciences Hungaricae Jomus"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0307-904X(78)90002-1","volume":"2","author":"J. M. Nelson","year":"1978","unstructured":"J. M. Nelson, ?A triangulation algorithm for arbitrary planar domains,?Appl. Math. Modelling 2:151?159 (September 1978).","journal-title":"Appl. Math. Modelling"},{"key":"CR24","volume-title":"Mathematical Ecology","author":"E. C. Pielou","year":"1977","unstructured":"E. C. Pielou,Mathematical Ecology (Wiley, New York, 1977)."},{"issue":"4","key":"CR25","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1145\/355759.355761","volume":"3","author":"M. J. D. Powell","year":"1977","unstructured":"M. J. D. Powell and M. A. Sabin, ?Piecewise quadratic approximations on triangles,?ACM Trans. Math. Software 3 (4):316?325 (December 1977).","journal-title":"ACM Trans. Math. Software"},{"issue":"2","key":"CR26","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"F. P. Preparata","year":"1977","unstructured":"F. P. Preparata and S. J. Hong, ?Convex hulls of finite sets of points in two and three dimensions,?Comm. ACM 20 (2):87?93 (February 1977).","journal-title":"Comm. ACM"},{"issue":"2","key":"CR27","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1111\/j.1538-4632.1973.tb01003.x","volume":"5","author":"D. Rhynsburger","year":"1973","unstructured":"D. Rhynsburger, ?Analytic delineation of Thiessen polygons,?Geographical Analysis 5 (2):133?144 (April 1973).","journal-title":"Geographical Analysis"},{"key":"CR28","unstructured":"C. A. Rogers,Packing and Covering (Cambridge University Press, 1964)."},{"issue":"9","key":"CR29","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1109\/TSMC.1978.4310055","volume":"8","author":"B. Schachter","year":"1978","unstructured":"B. Schachter, A. Rosenfeld, and L. S. Davis, ?Random mosaic models for textures,?IEEE Trans. Systems, Man, and Cybernetics 8 (9):694?702 (September 1978).","journal-title":"IEEE Trans. Systems, Man, and Cybernetics"},{"issue":"11","key":"CR30","doi-asserted-by":"crossref","first-page":"1078","DOI":"10.1109\/TC.1978.1675001","volume":"C-72","author":"B. J. Schacter","year":"1978","unstructured":"B. J. Schacter, ?Decomposition of polygons into convex sets,?IEEE Trans. Computers C-72 (11):1078?1082 (November 1978).","journal-title":"IEEE Trans. Computers"},{"key":"CR31","volume-title":"Computational Geometry","author":"M. I. Shamos","year":"1977","unstructured":"M. I.Shamos,Computational Geometry (Springer-Verlag, New York, 1977)."},{"key":"CR32","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey, ?Closest-point problems,?Proceedings of the 16th Annual Symposium on the Foundations of Computer Science, pp. 151?162 (October 1975).","DOI":"10.1109\/SFCS.1975.8"},{"issue":"3","key":"CR33","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1093\/comjnl\/21.3.243","volume":"21","author":"R. Sibson","year":"1978","unstructured":"R. Sibson, ?Locally equiangular triangulations,?Computer J. 21 (3):243?245 (August 1978).","journal-title":"Computer J."},{"key":"CR34","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/1011071","volume":"11","author":"B. Stears","year":"1969","unstructured":"B. Stears, ?Probability distribution of a network of triangles (Problem 67-15),?SIAM Rev. 11:399 (1969).","journal-title":"SIAM Rev."},{"key":"CR35","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1214\/aoms\/1177699064","volume":"38","author":"P. Switzer","year":"1967","unstructured":"P. Switzer, ?Reconstructing patterns from sampled data,?Ann. Math. Stat. 38:138?154 (1967).","journal-title":"Ann. Math. Stat."},{"key":"CR36","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.1175\/1520-0493(1911)39<1248a:DNGB>2.0.CO;2","volume":"39","author":"A. H. Thiessen","year":"1911","unstructured":"A. H. Thiessen, ?Precipitation averages for large areas,?Monthly Weather Rev. 39:1082?1084 (1911).","journal-title":"Monthly Weather Rev."},{"key":"CR37","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1515\/crll.1908.134.198","volume":"134","author":"G. Voronoi","year":"1908","unstructured":"G.Voronoi, ?Nouvelles applications des parametres continus \u00e0 la th\u00e9orie des formes quadratiques. Deuxi\u00e8me M\u00e9moire: Recherches sur les parallelloedres primitifs,?J. Reine Angew. Math. 134: 198?287 (1908).","journal-title":"J. Reine Angew. Math."}],"container-title":["International Journal of Computer &amp; Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00977785.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00977785\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00977785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,22]],"date-time":"2024-12-22T16:01:24Z","timestamp":1734883284000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00977785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980,6]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1980,6]]}},"alternative-id":["BF00977785"],"URL":"https:\/\/doi.org\/10.1007\/bf00977785","relation":{},"ISSN":["0091-7036","1573-7640"],"issn-type":[{"value":"0091-7036","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[1980,6]]}}}