{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:21:44Z","timestamp":1758824504024},"reference-count":23,"publisher":"Elsevier BV","issue":"3-4","license":[{"start":{"date-parts":[[2000,12,1]],"date-time":"2000-12-01T00:00:00Z","timestamp":975628800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4611,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Geometry"],"published-print":{"date-parts":[[2000,12]]},"DOI":"10.1016\/s0925-7721(00)00019-5","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T13:33:47Z","timestamp":1027604027000},"page":"153-163","source":"Crossref","is-referenced-by-count":5,"title":["Union and split operations on dynamic trapezoidal maps\u2606\u2606This work was partially supported by ESPRIT Basic Research Action r. 7141 (ALCOM II). A preliminary version appeared as [22]."],"prefix":"10.1016","volume":"17","author":[{"given":"Monique","family":"Teillaud","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0925-7721(00)00019-5_BIB001","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB002","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF02293035","article-title":"Applications of random sampling to on-line algorithms in computational geometry","volume":"8","author":"Boissonnat","year":"1992","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0925-7721(00)00019-5_BIB003","series-title":"Proc. 2nd Annu. ACM Sympos. Comput. Geom.","first-page":"260","article-title":"A hierarchical representation of objects: The Delaunay tree","author":"Boissonnat","year":"1986"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB004","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/0304-3975(93)90024-N","article-title":"On the randomized construction of the Delaunay tree","volume":"112","author":"Boissonnat","year":"1993","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0925-7721(00)00019-5_BIB005","series-title":"G\u00e9om\u00e9trie Algorithmique","author":"Boissonnat","year":"1995"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB006","series-title":"Algorithmic Geometry","author":"Boissonnat","year":"1998"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB007","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","article-title":"New applications of random sampling in computational geometry","volume":"2","author":"Clarkson","year":"1987","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0925-7721(00)00019-5_BIB008","series-title":"Proc. 4th Annu. ACM Sympos. Comput. Geom.","first-page":"1","article-title":"Applications of random sampling in computational geometry, II","author":"Clarkson","year":"1988"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB009","series-title":"Computing in Euclidean Geometry","first-page":"117","article-title":"Randomized geometric algorithms","volume":"1","author":"Clarkson","year":"1992"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB010","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","article-title":"Applications of random sampling in computational geometry, II","volume":"4","author":"Clarkson","year":"1989","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"10.1016\/S0925-7721(00)00019-5_BIB011","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0925-7721(92)90025-N","article-title":"Fully dynamic Delaunay triangulation in logarithmic expected time per operation","volume":"2","author":"Devillers","year":"1992","journal-title":"Computational Geometry"},{"issue":"3","key":"10.1016\/S0925-7721(00)00019-5_BIB012","first-page":"89","article-title":"Dynamic location in an arrangement of line segments in the plane","volume":"2","author":"Devillers","year":"1992","journal-title":"Algorithms Rev."},{"key":"10.1016\/S0925-7721(00)00019-5_BIB013","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1137\/S0097539791194094","article-title":"Dynamic perfect hashing: upper and lower bounds","volume":"23","author":"Dietzfelbinger","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0925-7721(00)00019-5_BIB014","series-title":"Proc. 4th Annu. Internat. Sympos. Algorithms Comput.","first-page":"21","article-title":"Remembering conflicts in history yields dynamic algorithms","volume":"762","author":"Dobrindt","year":"1993"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB015","series-title":"Towards a dynamic parallel database machine: data balancing techniques and pipeline, Technical Report RR 94-47","author":"Duboux","year":"1994"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB016","series-title":"Parallel Processing: CONPAR 92 \u2013 VAPP V","first-page":"545","article-title":"MIMD dictionary machines: from theory to practice","volume":"634","author":"Duboux","year":"1992"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB017","series-title":"Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci.","first-page":"216","article-title":"Randomized multidimensional search trees: Further results in dynamic sampling","author":"Mulmuley","year":"1991"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB018","series-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"Mulmuley","year":"1993"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB019","series-title":"Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci.","first-page":"197","article-title":"Dynamic maintenance of geometric structures made easy","author":"Schwarzkopf","year":"1991"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB020","series-title":"New Trends in Discrete and Computational Geometry","first-page":"37","article-title":"Backwards analysis of randomized geometric algorithms","volume":"10","author":"Seidel","year":"1993"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB021","series-title":"Towards Dynamic Randomized Algorithms in Computational Geometry","volume":"758","author":"Teillaud","year":"1993"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB022","series-title":"Proc. 7th Canad. Conf. Comput. Geom.","first-page":"181","article-title":"Union and split operations on dynamic trapezoidal maps","author":"Teillaud","year":"1995"},{"key":"10.1016\/S0925-7721(00)00019-5_BIB023","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","article-title":"Design and implementation of an efficient priority queue","volume":"10","author":"van Emde Boas","year":"1977","journal-title":"Math. Syst. Theory"}],"container-title":["Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0925772100000195?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0925772100000195?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T15:26:56Z","timestamp":1556119616000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0925772100000195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,12]]},"references-count":23,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2000,12]]}},"alternative-id":["S0925772100000195"],"URL":"https:\/\/doi.org\/10.1016\/s0925-7721(00)00019-5","relation":{},"ISSN":["0925-7721"],"issn-type":[{"value":"0925-7721","type":"print"}],"subject":[],"published":{"date-parts":[[2000,12]]}}}