{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T21:52:18Z","timestamp":1778622738002,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642401039","type":"print"},{"value":"9783642401046","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_42","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T01:36:30Z","timestamp":1373506590000},"page":"487-498","source":"Crossref","is-referenced-by-count":2,"title":["Unions of Onions: Preprocessing Imprecise Points for Fast Onion Layer Decomposition"],"prefix":"10.1007","author":[{"given":"Maarten","family":"L\u00f6ffler","sequence":"first","affiliation":[]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"42_CR1","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/090766437","volume":"40","author":"N. Ailon","year":"2011","unstructured":"Ailon, N., Chazelle, B., Clarkson, K.L., Liu, D., Mulzer, W., Seshadhri, C.: Self-improving algorithms. SIAM J. Comput.\u00a040(2), 350\u2013375 (2011)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"42_CR2","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF02187724","volume":"4","author":"N. Alon","year":"1989","unstructured":"Alon, N., Katchalski, M., Pulleyblank, W.R.: Cutting disjoint disks by straight lines. Discrete Comput. Geom.\u00a04(3), 239\u2013243 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"42_CR3","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 of Computing Systems\u00a038(4), 411\u2013423 (2005)","journal-title":"Theory of Computing Systems"},{"issue":"3","key":"42_CR4","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/s00453-010-9430-0","volume":"61","author":"K. Buchin","year":"2011","unstructured":"Buchin, K., L\u00f6ffler, M., Morin, P., Mulzer, W.: Preprocessing imprecise points for Delaunay triangulation: simplified and extended. Algorithmica\u00a061(3), 675\u2013693 (2011)","journal-title":"Algorithmica"},{"issue":"3","key":"42_CR5","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1706591.1706596","volume":"57","author":"T.M. Chan","year":"2010","unstructured":"Chan, T.M.: A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM\u00a057(3), Art. 16, 15p. (2010)","journal-title":"J. ACM"},{"issue":"4","key":"42_CR6","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/TIT.1985.1057060","volume":"31","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B.: On the convex layers of a planar set. IEEE Trans. Inform. Theory\u00a031(4), 509\u2013517 (1985)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"1","key":"42_CR7","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B., Guibas, L.J., Lee, D.T.: The power of geometric duality. BIT\u00a025(1), 76\u201390 (1985)","journal-title":"BIT"},{"issue":"1","key":"42_CR8","first-page":"30","volume":"2","author":"O. Devillers","year":"2011","unstructured":"Devillers, O.: Delaunay triangulation of imprecise points: preprocess and actually get a fast query time. J. Comput. Geom.\u00a02(1), 30\u201345 (2011)","journal-title":"J. Comput. Geom."},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Eddy, W.F.: Convex hull peeling. In: Proc. 5th Symp. Comp. Statistics (COMPSTAT), pp. 42\u201347 (1982)","DOI":"10.1007\/978-3-642-51461-6_4"},{"issue":"4","key":"42_CR10","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.comgeo.2012.03.004","volume":"46","author":"E. Ezra","year":"2013","unstructured":"Ezra, E., Mulzer, W.: Convex hull of points lying on lines in o(nlogn) time after preprocessing. Comput. Geom.\u00a046(4), 417\u2013434 (2013)","journal-title":"Comput. Geom."},{"issue":"2","key":"42_CR11","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."},{"issue":"1","key":"42_CR12","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. Inform. Process. Lett.\u00a0109(1), 54\u201356 (2008)","journal-title":"Inform. Process. Lett."},{"key":"42_CR13","unstructured":"Hoffmann, M., Erlebach, T., Krizanc, D., Mihal\u00e1k, M., Raman, R.: Computing minimum spanning trees with uncertainty. In: Proc. 25th Sympos. Theoret. Aspects Comput. Sci. (STACS), pp. 277\u2013288 (2008)"},{"key":"42_CR14","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1214\/aoms\/1177692459","volume":"43","author":"P.J. Huber","year":"1972","unstructured":"Huber, P.J.: Robust statistics: A review. Ann. Math. Statist.\u00a043, 1041\u20131067 (1972)","journal-title":"Ann. Math. Statist."},{"key":"42_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/3-540-60220-8_61","volume-title":"Algorithms and Data Structures","author":"D. Kirkpatrick","year":"1995","unstructured":"Kirkpatrick, D., Snoeyink, J.: Computing common tangents without a separating line. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol.\u00a0955, pp. 183\u2013193. Springer, Heidelberg (1995)"},{"issue":"7","key":"42_CR16","doi-asserted-by":"publisher","first-page":"2990","DOI":"10.1137\/090753620","volume":"39","author":"M. Kreveld van","year":"2010","unstructured":"van Kreveld, M., L\u00f6ffler, M., Mitchell, J.S.B.: Preprocessing imprecise points and splitting triangulations. SIAM J. Comput.\u00a039(7), 2990\u20133000 (2010)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"42_CR17","doi-asserted-by":"publisher","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.\u00a043(3), 234\u2013242 (2010)","journal-title":"Comput. Geom."},{"issue":"3","key":"42_CR18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J. Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Efficient partition trees. Discrete Comput. Geom.\u00a08(3), 315\u2013334 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press (1995)","DOI":"10.1017\/CBO9780511814075"},{"key":"42_CR20","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0020-0190(96)00116-0","volume":"59","author":"F. Nielsen","year":"1996","unstructured":"Nielsen, F.: Output-sensitive peeling of convex and maximal layers. Inform. Process. Lett.\u00a059, 255\u2013259 (1996)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"42_CR21","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M.H. Overmars","year":"1981","unstructured":"Overmars, M.H., van Leeuwen, J.: Maintenance of configurations in the plane. J. Comput. System Sci.\u00a023(2), 166\u2013204 (1981)","journal-title":"J. Comput. System Sci."},{"key":"42_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/3-540-48375-6_55","volume-title":"Computer Analysis of Images and Patterns","author":"T. Suk","year":"1999","unstructured":"Suk, T., Flusser, J.: Convex layers: A new tool for recognition of projectively deformed point sets. In: Solina, F., Leonardis, A. (eds.) CAIP 1999. LNCS, vol.\u00a01689, pp. 454\u2013461. Springer, Heidelberg (1999)"},{"key":"42_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-642-25591-5_57","volume-title":"Algorithms and Computation","author":"K.-C.R. Tseng","year":"2011","unstructured":"Tseng, K.-C.R., Kirkpatrick, D.: Input-thrifty extrema testing. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 554\u2013563. Springer, Heidelberg (2011)"}],"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-40104-6_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T14:33:23Z","timestamp":1557930803000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}