{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:00:15Z","timestamp":1725494415891},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648482"},{"type":"electronic","value":"9783540685302"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-68530-8_15","type":"book-chapter","created":{"date-parts":[[2007,11,8]],"date-time":"2007-11-08T22:14:16Z","timestamp":1194560056000},"page":"175-186","source":"Crossref","is-referenced-by-count":1,"title":["A Robust Region Approach to the Computation of Geometric Graphs (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Fabrizio","family":"d\u2019Amore","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo G.","family":"Franciosa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"issue":"5","key":"15_CR1","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/BF02574698","volume":"6","author":"P. K. Agarwal","year":"1991","unstructured":"P. K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete Comput. Geom., 6(5):407\u2013422, 1991.","journal-title":"Discrete Comput. Geom."},{"key":"15_CR2","unstructured":"J. D. Boissonnat and F. Preparata. Robust plane sweep for intersecting segments. Technical Report 3270, INRIA, Sophia Antipolis, 1997."},{"key":"15_CR3","unstructured":"C. Burnikel. Exact Computation of Voronoi Diagrams and Line Segment Intersections. Ph.D thesis, Universit\u00e4t des Saarlandes, Mar. 1996."},{"key":"15_CR4","unstructured":"P. B. Callahan and S. R. Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Proc. 4th ACM-SIAM Sympos. Discrete Algorithms, pages 291\u2013300, 1993."},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1137\/0205051","volume":"5","author":"D. Cheriton","year":"1976","unstructured":"D. Cheriton and R. E. Tarjan. Finding minimum spanning trees. SIAM J. Comput., 5:724\u2013742, 1976.","journal-title":"SIAM J. Comput."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"O. Devillers, G. Liotta, R. Tamassia, and F. P. Preparata. Cecking the convexity of polytopes and the planarity of subdivisions. In Algorithms and Data Structures (Proc. WADS 97), volume 1272 of Lecture Notes Comput. Sci., pages 186\u2013199. Springer-Verlag, 1997.","DOI":"10.1007\/3-540-63307-3_59"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. In Proc. 16th Annu. ACM Sympos. Theory Comput., pages 135\u2013143, 1984.","DOI":"10.1145\/800057.808675"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/282918.282923","volume":"4","author":"L. J. Guibas","year":"1985","unstructured":"L. J. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph., 4:74\u2013123, 1985.","journal-title":"ACM Trans. Graph."},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF01178779","volume":"29","author":"K. Hinrichs","year":"1992","unstructured":"K. Hinrichs, J. Nievergelt, and P. Schorn. An all-round sweep algorithm for 2-dimensional nearest-neighbor problems. Acta Informatica, 29:383\u2013394, 1992.","journal-title":"Acta Informatica"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/99902.99905","volume":"10","author":"M. Karasick","year":"1991","unstructured":"M. Karasick, D. Lieber, and L. R. Nackman. Effcient Delaunay triangulations using rational arithmetic. ACM Trans. Graph., 10:71\u201391, 1991.","journal-title":"ACM Trans. Graph."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF02247943","volume":"40","author":"J. Katajainen","year":"1987","unstructured":"J. Katajainen. The region approach for computing relative neighborhood graphs in the L p metric. Computing, 40:147\u2013161, 1987.","journal-title":"Computing"},{"key":"15_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/3-540-63397-9_26","volume-title":"Proc. of ESA 97","author":"D. Krznaric","year":"1997","unstructured":"D. Krznaric, C. Levcopoulos, and B. J. Nilsson. Minimum spanning trees in d dimensions. In Proc. of ESA 97, number 1284 in Lecture Notes in Computer Science, pages 341\u2013349. Springer, 1997."},{"key":"15_CR13","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0925-7721(94)90018-3","volume":"4","author":"A. Lingas","year":"1994","unstructured":"A. Lingas. A linear-time construction of the relative neighborhood graph from the Delaunay triangulation. Comput. Geom. Theory Appl., 4:199\u2013208, 1994.","journal-title":"Comput. Geom. Theory Appl."},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"G. Liotta, F. P. Preparata, and R. Tamassia. Robust proximity queries: an illustration of degree-driven algorithm design. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 156\u2013165, 1997.","DOI":"10.1145\/262839.262922"},{"key":"15_CR15","unstructured":"E. P. M\u00fccke. Detri 2.2: A robust implementation for 3D triangulations. Manuscript, available at URL: http:\/\/www.geom.umn.edu:80\/software\/cglist\/lowdvod.html, 1996."},{"key":"15_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, NY, 1985."},{"key":"15_CR17","series-title":"Informatik-Dissertationen ETH Z\u00fcrich","volume-title":"Robust Algorithms in a Program Library for Geometric Computation","author":"P. Schorn","year":"1991","unstructured":"P. Schorn. Robust Algorithms in a Program Library for Geometric Computation, volume 32 of Informatik-Dissertationen ETH Z\u00fcrich. Verlag der Fachvereine, Z\u00fcrich, 1991."},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1145\/2402.322386","volume":"30","author":"K. J. Supowit","year":"1983","unstructured":"K. J. Supowit. The relative neighborhood graph with an application to minimum spanning trees. J. ACM, 30:428\u2013448, 1983.","journal-title":"J. ACM"},{"key":"15_CR19","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1137\/0217035","volume":"17","author":"P. M. Vaidya","year":"1988","unstructured":"P. M. Vaidya. Minimum spanning trees in k-dimensional space. SIAM J. Comput., 17:572\u2013582, 1988.","journal-title":"SIAM J. Comput."},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"P. M. Vaidya","year":"1989","unstructured":"P. M. Vaidya. An O(n log n) algorithm for the all-nearest-neighbors problem. Discrete Comput. Geom., 4:101\u2013115, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"15_CR21","unstructured":"Y. C. Wee, S. Chaiken, and D. E. Willard. General metrics and angle restricted voronoi diagrams. Technical Report 88-31, Comp. Sci. Dpt., Univ. at Albany, November 1988."},{"key":"15_CR22","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A. C. Yao","year":"1982","unstructured":"A. C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11:721\u2013736, 1982.","journal-title":"SIAM J. Comput."},{"key":"15_CR23","first-page":"653","volume-title":"Handbook of Discrete and Computational Geometry","author":"C. K. Yap","year":"1997","unstructured":"C. K. Yap. Robust geometric computation. In J. E. Goodman and J. O\u2019Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 35, pages 653\u2013668. CRC Press LLC, Boca Raton, FL, 1997."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA\u2019 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-68530-8_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T08:28:12Z","timestamp":1556958492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-68530-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648482","9783540685302"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-68530-8_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}