{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T19:40:49Z","timestamp":1743018049145,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319130743"},{"type":"electronic","value":"9783319130750"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_57","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:37:06Z","timestamp":1415983026000},"page":"726-737","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Ham-Sandwich Cuts for Abstract Order Types"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Felsner","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Pilz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,8]]},"reference":[{"key":"57_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-642-45030-3_2","volume-title":"Algorithms and Computation","author":"O Aichholzer","year":"2013","unstructured":"Aichholzer, O., Hackl, T., Korman, M., Pilz, A., Vogtenhuber, B.: Geodesic-Preserving Polygon Simplification. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 11\u201321. Springer, Heidelberg (2013)"},{"key":"57_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/978-3-642-32241-9_19","volume-title":"Computing and Combinatorics","author":"O Aichholzer","year":"2012","unstructured":"Aichholzer, O., Korman, M., Pilz, A., Vogtenhuber, B.: Geodesic Order Types. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 216\u2013227. Springer, Heidelberg (2012)"},{"issue":"8","key":"57_CR3","doi-asserted-by":"publisher","first-page":"970","DOI":"10.1016\/j.comgeo.2013.05.001","volume":"46","author":"O Aichholzer","year":"2013","unstructured":"Aichholzer, O., Miltzow, T., Pilz, A.: Extreme point and halving edge search in abstract order types. Comput. Geom. 46(8), 970\u2013978 (2013)","journal-title":"Comput. Geom."},{"issue":"2","key":"57_CR4","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02522822","volume":"17","author":"F Avnaim","year":"1997","unstructured":"Avnaim, F., Boissonnat, J.D., Devillers, O., Preparata, F.P., Yvinec, M.: Evaluating signs of determinants using single-precision arithmetic. Algorithmica 17(2), 111\u2013132 (1997)","journal-title":"Algorithmica"},{"issue":"4","key":"57_CR5","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. System Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"57_CR6","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0925-7721(99)00057-7","volume":"16","author":"JD Boissonnat","year":"2000","unstructured":"Boissonnat, J.D., Snoeyink, J.: Efficient algorithms for line and curve segment intersection using restricted predicates. Comput. Geom. 16(1), 35\u201352 (2000)","journal-title":"Comput. Geom."},{"key":"57_CR7","doi-asserted-by":"crossref","unstructured":"Bose, P., Demaine, E.D., Hurtado, F., Iacono, J., Langerman, S., Morin, P.: Geodesic ham-sandwich cuts. In: SoCG. pp. 1\u20139. ACM (2004)","DOI":"10.1145\/997817.997821"},{"issue":"1","key":"57_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J.: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 38(1), 165\u2013194 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"57_CR9","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0022-0000(91)90013-U","volume":"42","author":"H Edelsbrunner","year":"1991","unstructured":"Edelsbrunner, H., Guibas, L.J.: Corrigendum: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 42(2), 249\u2013251 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"57_CR10","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0747-7171(86)80020-7","volume":"2","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Waupotitsch, R.: Computing a ham-sandwich cut in two dimensions. J. Symb. Comput. 2(2), 171\u2013178 (1986)","journal-title":"J. Symb. Comput."},{"key":"57_CR11","unstructured":"Erickson, J.G.: Lower Bounds for Fundamental Geometric Problems. Ph.D. thesis, University of California at Berkeley (1996)"},{"key":"57_CR12","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/BF02574389","volume":"12","author":"B G\u00e4rtner","year":"1994","unstructured":"G\u00e4rtner, B., Welzl, E.: Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements. Discrete Comput. Geom. 12, 399\u2013432 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"57_CR13","doi-asserted-by":"crossref","unstructured":"Goodman, J.E., Pollack, R.: On the combinatorial classification of nondegenerate configurations in the plane. J. Comb. Theory, Ser. A 29(2), 220\u2013235 (1980)","DOI":"10.1016\/0097-3165(80)90011-4"},{"issue":"3","key":"57_CR14","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/0212032","volume":"12","author":"JE Goodman","year":"1983","unstructured":"Goodman, J.E., Pollack, R.: Multidimensional sorting. SIAM J. Comput. 12(3), 484\u2013507 (1983)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"57_CR15","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0097-3165(84)90050-5","volume":"37","author":"JE Goodman","year":"1984","unstructured":"Goodman, J.E., Pollack, R.: Semispaces of configurations, cell complexes of arrangements. J. Combin. Theory Ser. A 37(3), 257\u2013293 (1984)","journal-title":"J. Combin. Theory Ser. A"},{"key":"57_CR16","doi-asserted-by":"crossref","unstructured":"Goodman, J.E., Pollack, R.: Allowable sequences and order types in discrete and computational geometry. In: Pach, J. (ed.) New Trends in Discrete and Computational Geometry, pp. 103\u2013134. Springer (1993).","DOI":"10.1007\/978-3-642-58043-7_6"},{"key":"57_CR17","doi-asserted-by":"crossref","unstructured":"Knuth, D.E.: Axioms and Hulls, vol. 606, LNCS. Springer (1992)","DOI":"10.1007\/3-540-55611-7"},{"key":"57_CR18","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/BF02574017","volume":"11","author":"CY Lo","year":"1994","unstructured":"Lo, C.Y., Matou\u0161ek, J., Steiger, W.: Algorithms for ham-sandwich cuts. Discrete Comput. Geom. 11, 433\u2013452 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"57_CR19","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Approximations and optimal geometric divide-and-conquer. In: STOC, pp. 505\u2013511. ACM (1991)","DOI":"10.1145\/103418.103470"},{"key":"57_CR20","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Epsilon-nets and computational geometry. In: Pach, J. (ed.) New Trends in Discrete and Computational Geometry, pp. 69\u201389. Springer (1993)","DOI":"10.1007\/978-3-642-58043-7_4"},{"issue":"2","key":"57_CR21","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jcss.1995.1018","volume":"50","author":"J Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: Approximations and optimal geometric divide-and-conquer. J. Comput. System Sci. 50(2), 203\u2013208 (1995)","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"57_CR22","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0196-6774(85)90011-2","volume":"6","author":"N Megiddo","year":"1985","unstructured":"Megiddo, N.: Partitioning with two lines in the plane. J. Algorithms 6(3), 430\u2013433 (1985)","journal-title":"J. Algorithms"},{"key":"57_CR23","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11615798_1","volume-title":"Automated Deduction in Geometry","author":"LI Meikle","year":"2006","unstructured":"Meikle, L.I., Fleuriot, J.D.: Mechanical Theorem Proving in Computational Geometry. In: Hong, H., Wang, D. (eds.) ADG 2004. LNCS (LNAI), vol. 3763, pp. 1\u201318. Springer, Heidelberg (2006)"},{"key":"57_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/3-540-44755-5_24","volume-title":"Theorem Proving in Higher Order Logics","author":"D Pichardie","year":"2001","unstructured":"Pichardie, D., Bertot, Y.: Formalizing Convex Hull Algorithms. In: Boulton, R.J., Jackson, P.B. (eds.) TPHOLs 2001. LNCS, vol. 2152, pp. 346\u2013361. Springer, Heidelberg (2001)"},{"key":"57_CR25","unstructured":"Pilz, A.: On the Complexity of Problems on Order Types and Geometric Graphs. Ph.D. thesis, Graz University of Technology (2014)"},{"issue":"1","key":"57_CR26","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00373-007-0716-1","volume":"23","author":"S Roy","year":"2007","unstructured":"Roy, S., Steiger, W.: Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem. Graphs Combin. 23(1), 331\u2013341 (2007)","journal-title":"Graphs Combin."},{"key":"57_CR27","doi-asserted-by":"crossref","unstructured":"Snoeyink, J., Hershberger, J.: Sweeping arrangements of curves. In: SoCG, pp. 354\u2013363 (1989)","DOI":"10.1145\/73833.73872"},{"key":"57_CR28","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Ya.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T00:43:07Z","timestamp":1674175387000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}