{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:33:28Z","timestamp":1725536008761},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642033667"},{"type":"electronic","value":"9783642033674"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03367-4_12","type":"book-chapter","created":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T07:56:42Z","timestamp":1248076602000},"page":"131-143","source":"Crossref","is-referenced-by-count":0,"title":["Delaunay Triangulation of Imprecise Points Simplified and Extended"],"prefix":"10.1007","author":[{"given":"Kevin","family":"Buchin","sequence":"first","affiliation":[]},{"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"12_CR1","doi-asserted-by":"publisher","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 Journal on Computing\u00a038(3), 899\u2013921 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR2","unstructured":"Bandyopadhyay, D., Snoeyink, J.: Almost-Delaunay simplices: Nearest neighbor relations for imprecise points. In: SODA, pp. 403\u2013412 (2004)"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: STOC, pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"issue":"3","key":"12_CR4","doi-asserted-by":"publisher","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. System Sci.\u00a048(3), 384\u2013409 (1994)","journal-title":"J. Comput. System Sci."},{"issue":"6","key":"12_CR5","doi-asserted-by":"publisher","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. Internat. J. Comput. Geom. Appl.\u00a09(6), 517\u2013532 (1999)","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"4","key":"12_CR6","doi-asserted-by":"publisher","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.\u00a038(4), 411\u2013423 (2005)","journal-title":"Theory Comput. Syst."},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Disc. and Comp. Geometry\u00a06, 485\u2013524 (1991)","journal-title":"Disc. and Comp. Geometry"},{"issue":"1","key":"12_CR8","doi-asserted-by":"publisher","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\u00a034(1), 39\u201346 (2002)","journal-title":"Algorithmica"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Mulzer, W.: Computing hereditary convex structures. To appear in SoCG (2009)","DOI":"10.1145\/1542362.1542374"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Seshadhri, C.: Self-improving algorithms for Delaunay triangulations. In: SoCG, pp. 148\u2013155 (2008)","DOI":"10.1145\/1377676.1377700"},{"issue":"3","key":"12_CR11","doi-asserted-by":"publisher","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\u00a028(3), 353\u2013366 (2000)","journal-title":"Algorithmica"},{"key":"12_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational geometry","author":"M. Berg de","year":"2000","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational geometry, 3rd edn. Springer, Berlin (2000); Algorithms and applications","edition":"3"},{"issue":"2","key":"12_CR13","doi-asserted-by":"publisher","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 der Stappen, A.F., Vleugels, J.: Guarding scenes against invasive hypercubes. Computational Geometry: Theory and Applications\u00a026(2), 99\u2013117 (2003)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"1","key":"12_CR14","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s00453-002-0961-x","volume":"34","author":"M. Berg de","year":"2002","unstructured":"de Berg, M., van der Stappen, A.F., Vleugels, J., Katz, M.J.: Realistic input models for geometric algorithms. Algorithmica\u00a034(1), 81\u201397 (2002)","journal-title":"Algorithmica"},{"issue":"3","key":"12_CR15","doi-asserted-by":"publisher","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. Internat. J. Comput. Geom. Appl.\u00a05(3), 327\u2013337 (1995)","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"2","key":"12_CR16","doi-asserted-by":"publisher","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. Internat. J. Comput. Geom. Appl.\u00a04(2), 153\u2013163 (1994)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Salesin, D., Stolfi, J.: Epsilon geometry: building robust algorithms from imprecise computations. In: SoCG, pp. 208\u2013217 (1989)","DOI":"10.1145\/73833.73857"},{"key":"12_CR18","doi-asserted-by":"publisher","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\u00a09, 534\u2013560 (1993)","journal-title":"Algorithmica"},{"issue":"1","key":"12_CR19","doi-asserted-by":"publisher","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. Inf. Process. Lett.\u00a0109(1), 54\u201356 (2008)","journal-title":"Inf. Process. Lett."},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G.: Efficient computation of continuous skeletons. In: FOCS, pp. 18\u201327 (1979)","DOI":"10.1109\/SFCS.1979.15"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"L\u00f6ffler, M., Snoeyink, J.: Delaunay triangulations of imprecise points in linear time after preprocessing. In: SoCG, pp. 298\u2013304 (2008)","DOI":"10.1145\/1377676.1377727"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/BF02574375","volume":"12","author":"V.T. Rajan","year":"1994","unstructured":"Rajan, V.T.: Optimality of the Delaunay triangulation in \u211d d . Disc. and Comp. Geometry\u00a012, 189\u2013202 (1994)","journal-title":"Disc. and Comp. Geometry"},{"key":"12_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/978-3-540-92182-0_49","volume-title":"Algorithms and Computation","author":"M..J. Kreveld van","year":"2008","unstructured":"van Kreveld, M.J., L\u00f6ffler, M., Mitchell, J.S.B.: Preprocessing imprecise points and splitting triangulations. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 544\u2013555. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03367-4_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T15:28:52Z","timestamp":1558452532000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03367-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033667","9783642033674"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03367-4_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}