{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:22:05Z","timestamp":1760440925855},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,11]]},"DOI":"10.1007\/s00453-010-9430-0","type":"journal-article","created":{"date-parts":[[2010,7,27]],"date-time":"2010-07-27T15:06:47Z","timestamp":1280243207000},"page":"674-693","source":"Crossref","is-referenced-by-count":20,"title":["Preprocessing Imprecise Points for Delaunay Triangulation: Simplified and Extended"],"prefix":"10.1007","volume":"61","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,7,28]]},"reference":[{"issue":"3","key":"9430_CR1","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1137\/060669474","volume":"38","author":"B. Aronov","year":"2008","unstructured":"Aronov, B., Har-Peled, S.: On approximating the depth and related problems. SIAM J. Comput. 38(3), 899\u2013921 (2008)","journal-title":"SIAM J. Comput."},{"key":"9430_CR2","unstructured":"Bandyopadhyay, D., Snoeyink, J.: Almost-Delaunay simplices: nearest neighbor relations for imprecise points. In: Proc. 15th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pp. 403\u2013412 (2004)"},{"key":"9430_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proc. 16th Annu. ACM Sympos. Theory Comput. (STOC), pp.\u00a080\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"issue":"3","key":"9430_CR4","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s004530010047","volume":"28","author":"M. Berg de","year":"2000","unstructured":"de Berg, M.: Linear size binary space partitions for uncluttered scenes. Algorithmica 28(3), 353\u2013366 (2000)","journal-title":"Algorithmica"},{"key":"9430_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"issue":"2","key":"9430_CR6","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0925-7721(03)00016-6","volume":"26","author":"M. Berg de","year":"2003","unstructured":"de Berg, M., David, H., Katz, M.J., Overmars, M.H., van\u00a0der Stappen, A.F., Vleugels, J.: Guarding scenes against invasive hypercubes. Comput. Geom. Theory Appl. 26(2), 99\u2013117 (2003)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"9430_CR7","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s00453-002-0961-x","volume":"34","author":"M. Berg de","year":"2002","unstructured":"de Berg, M., van\u00a0der Stappen, A.F., Vleugels, J., Katz, M.J.: Realistic input models for geometric algorithms. Algorithmica 34(1), 81\u201397 (2002)","journal-title":"Algorithmica"},{"issue":"3","key":"9430_CR8","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(05)80059-5","volume":"48","author":"M. Bern","year":"1994","unstructured":"Bern, M., Eppstein, D., Gilbert, J.: Provably good mesh generation. J. Comput. Syst. Sci. 48(3), 384\u2013409 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"9430_CR9","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1142\/S0218195999000303","volume":"9","author":"M. Bern","year":"1999","unstructured":"Bern, M., Eppstein, D., Teng, S.H.: Parallel construction of quadtrees and quality triangulations. Int. J. Comput. Geom. Appl. 9(6), 517\u2013532 (1999)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"9430_CR10","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s00224-004-1180-4","volume":"38","author":"R. Bruce","year":"2005","unstructured":"Bruce, R., Hoffmann, M., Krizanc, D., Raman, R.: Efficient update strategies for geometric computing with uncertainty. Theory Comput. Syst. 38(4), 411\u2013423 (2005)","journal-title":"Theory Comput. Syst."},{"key":"9430_CR11","doi-asserted-by":"crossref","unstructured":"Buchin, K., Mulzer, W.: Delaunay triangulations in O(sort(n)) time and more. In: Proc. 50th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp.\u00a0139\u2013148 (2009)","DOI":"10.1109\/FOCS.2009.53"},{"issue":"1","key":"9430_CR12","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42(1), 67\u201390 (1995)","journal-title":"J. ACM"},{"issue":"5","key":"9430_CR13","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.ipl.2008.02.008","volume":"107","author":"T.M. Chan","year":"2008","unstructured":"Chan, T.M.: Well-separated pair decomposition in linear time? Inform. Process. Lett. 107(5), 138\u2013141 (2008)","journal-title":"Inform. Process. Lett."},{"key":"9430_CR14","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 485\u2013524 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9430_CR15","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s00453-002-0939-8","volume":"34","author":"B. Chazelle","year":"2002","unstructured":"Chazelle, B., Devillers, O., Hurtado, F., Mora, M., Sacrist\u00e1n, V., Teillaud, M.: Splitting a Delaunay triangulation in linear time. Algorithmica 34(1), 39\u201346 (2002)","journal-title":"Algorithmica"},{"key":"9430_CR16","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Mulzer, W.: Computing hereditary convex structures. In: Proc. 25th Annu. ACM Sympos. Comput. Geom. (SoCG), pp. 61\u201370 (2009)","DOI":"10.1145\/1542362.1542374"},{"key":"9430_CR17","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Seshadhri, C.: Self-improving algorithms for Delaunay triangulations. In: Proc. 24th Annu. ACM Sympos. Comput. Geom. (SoCG), pp. 148\u2013155 (2008)","DOI":"10.1145\/1377676.1377700"},{"issue":"3","key":"9430_CR18","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1142\/S0218195995000192","volume":"5","author":"H.N. Djidjev","year":"1995","unstructured":"Djidjev, H.N., Lingas, A.: On computing Voronoi diagrams for sorted point sets. Int. J. Comput. Geom. Appl. 5(3), 327\u2013337 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"9430_CR19","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF02574002","volume":"11","author":"D. Eppstein","year":"1994","unstructured":"Eppstein, D.: Approximating the minimum weight Steiner triangulation. Discrete Comput. Geom. 11(2), 163\u2013191 (1994)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9430_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R.A. Finkel","year":"1974","unstructured":"Finkel, R.A., Bentley, J.L.: Quad trees: a data structure for retrieval on composite keys. Acta Inform. 4(1), 1\u20139 (1974)","journal-title":"Acta Inform."},{"issue":"2","key":"9430_CR21","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1142\/S0218195994000100","volume":"4","author":"P.G. Franciosa","year":"1994","unstructured":"Franciosa, P.G., Gaibisso, C., Gambosi, G., Talamo, M.: A convex hull algorithm for points with approximately known positions. Int. J. Comput. Geom. Appl. 4(2), 153\u2013163 (1994)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9430_CR22","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Salesin, D., Stolfi, J.: Epsilon geometry: building robust algorithms from imprecise computations. In: Proc. 5th Annu. ACM Sympos. Comput. Geom. (SoCG), pp.\u00a0208\u2013217 (1989)","DOI":"10.1145\/73833.73857"},{"key":"9430_CR23","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1007\/BF01190154","volume":"9","author":"L.J. Guibas","year":"1993","unstructured":"Guibas, L.J., Salesin, D., Stolfi, J.: Constructing strongly convex approximate hulls with inaccurate primitives. Algorithmica 9, 534\u2013560 (1993)","journal-title":"Algorithmica"},{"issue":"1","key":"9430_CR24","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.ipl.2008.09.016","volume":"109","author":"M. Held","year":"2008","unstructured":"Held, M., Mitchell, J.S.B.: Triangulating input-constrained planar point sets. Inform. Process. Lett. 109(1), 54\u201356 (2008)","journal-title":"Inform. Process. Lett."},{"key":"9430_CR25","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G.: Efficient computation of continuous skeletons. In: Proc. 20th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 18\u201327 (1979)","DOI":"10.1109\/SFCS.1979.15"},{"issue":"4","key":"9430_CR26","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/j.comgeo.2009.01.010","volume":"43","author":"M. Kreveld van","year":"2010","unstructured":"van Kreveld, M., L\u00f6ffler, M.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom. Theory Appl. 43(4), 419\u2013433 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9430_CR27","doi-asserted-by":"crossref","unstructured":"van Kreveld, M.J., L\u00f6ffler, M., Mitchell, J.S.B.: Preprocessing imprecise points and splitting triangulations. In: Proc. 19th Annu. Internat. Sympos. Algorithms Comput. (ISAAC), pp. 544\u2013555 (2008)","DOI":"10.1007\/978-3-540-92182-0_49"},{"key":"9430_CR28","unstructured":"Kruger, H.: Basic measures for imprecise point sets in \u211d d . Master\u2019s thesis, Utrecht University (2008)"},{"issue":"3","key":"9430_CR29","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.comgeo.2008.12.007","volume":"43","author":"M. L\u00f6ffler","year":"2010","unstructured":"L\u00f6ffler, M., Snoeyink, J.: Delaunay triangulation of imprecise points in linear time after preprocessing. Comput. Geom. Theory Appl. 43(3), 234\u2013242 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9430_CR30","series-title":"LNCS","first-page":"252","volume-title":"Jap. Conf. on Discrete and Comput. Geom.","author":"T. Nagai","year":"2000","unstructured":"Nagai, T., Tokura, N.: Tight error bounds of geometric problems on convex objects with imprecise coordinates. In: Jap. Conf. on Discrete and Comput. Geom. LNCS, vol. 2098, pp. 252\u2013263. Springer, Berlin (2000)"},{"key":"9430_CR31","unstructured":"Ostrovsky-Berman, Y., Joskowicz, L.: Uncertainty envelopes. In: Proc. 21st European Workshop Comput. Geom. (EWCG), pp.\u00a0175\u2013178 (2005)"},{"key":"9430_CR32","doi-asserted-by":"crossref","unstructured":"van\u00a0der Stappen, A.F.: Motion planning amidst fat obstacles. Ph.D. thesis, Dept. Comput. Sci., Utrecht Univ., Utrecht, the Netherlands (1994)","DOI":"10.1145\/177424.177453"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00453-010-9430-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T19:02:21Z","timestamp":1559329341000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9430-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,28]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["9430"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9430-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,28]]}}}