{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:55Z","timestamp":1740109255670,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T00:00:00Z","timestamp":1480291200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["J-3847-N35"],"award-info":[{"award-number":["J-3847-N35"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00453-016-0246-4","type":"journal-article","created":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T11:12:46Z","timestamp":1480331566000},"page":"234-257","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","volume":"80","author":[{"given":"Stefan","family":"Felsner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6059-1821","authenticated-orcid":false,"given":"Alexander","family":"Pilz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,28]]},"reference":[{"issue":"3","key":"246_CR1","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1137\/S0097539703433900","volume":"34","author":"PK Agarwal","year":"2005","unstructured":"Agarwal, P.K., Sharir, M.: Pseudo-line arrangements: duality, algorithms, and applications. SIAM J. Comput. 34(3), 526\u2013552 (2005)","journal-title":"SIAM J. Comput."},{"key":"246_CR2","doi-asserted-by":"crossref","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.) ISAAC. LNCS, vol. 8283, pp. 11\u201321. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-45030-3_2"},{"key":"246_CR3","doi-asserted-by":"crossref","unstructured":"Aichholzer, O., Korman, M., Pilz, A., Vogtenhuber, B.: Geodesic order types. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON. LNCS, vol. 7434. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32241-9_19"},{"issue":"8","key":"246_CR4","doi-asserted-by":"crossref","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":"246_CR5","doi-asserted-by":"crossref","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"},{"key":"246_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0095-8956(77)90055-7","volume":"23","author":"R Bland","year":"1977","unstructured":"Bland, R.: A combinatorial abstraction of linear programming. J. Comb. Theory B 23, 33\u201357 (1977)","journal-title":"J. Comb. Theory B"},{"issue":"4","key":"246_CR7","doi-asserted-by":"crossref","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. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"246_CR8","doi-asserted-by":"crossref","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":"246_CR9","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":"3","key":"246_CR10","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1006\/jagm.1996.0060","volume":"21","author":"B Chazelle","year":"1996","unstructured":"Chazelle, B., Matou\u0161ek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21(3), 579\u2013597 (1996)","journal-title":"J. Algorithms"},{"issue":"1","key":"246_CR11","doi-asserted-by":"crossref","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":"246_CR12","doi-asserted-by":"crossref","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":"1","key":"246_CR13","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/77635.77639","volume":"9","author":"H Edelsbrunner","year":"1990","unstructured":"Edelsbrunner, H., M\u00fccke, E.P.: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph. 9(1), 66\u2013104 (1990)","journal-title":"ACM Trans. Graph."},{"issue":"2","key":"246_CR14","doi-asserted-by":"crossref","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."},{"issue":"1","key":"246_CR15","first-page":"45","volume":"11","author":"J Erickson","year":"2009","unstructured":"Erickson, J., Hurtado, F., Morin, P.: Centerpoint theorems for wedges. Discrete Math. Theor. Comput. Sci. 11(1), 45\u201354 (2009)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"246_CR16","unstructured":"Erickson, J.G.: Lower bounds for fundamental geometric problems. Ph.D. Thesis, University of California at Berkeley (1996)"},{"key":"246_CR17","doi-asserted-by":"crossref","unstructured":"Felsner, S., Pilz, A.: Ham-Sandwich cuts for abstract order types. In: Algorithms and Computation\u201425th International Symposium, ISAAC 2014, Jeonju, Korea, December 15\u201317, 2014, Proceedings, LNCS, vol. 8889, pp. 726\u2013737. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-13075-0_57"},{"key":"246_CR18","unstructured":"Fukuda, K.: Oriented matroid programming. Ph.D. thesis, University of Waterloo, Canada (1981)"},{"key":"246_CR19","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BF02574389","volume":"12","author":"B G\u00e4rtner","year":"1994","unstructured":"G\u00e4rtner, B., Welzl, E.: Vapnik\u2013Chervonenkis dimension and (pseudo-)hyperplane arrangements. Discrete Comput. Geom. 12, 399\u2013432 (1994)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"246_CR20","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0012-365X(80)90096-5","volume":"32","author":"JE Goodman","year":"1980","unstructured":"Goodman, J.E.: Proof of a conjecture of Burr, Gr\u00fcnbaum, and Sloane. Discrete Math. 32(1), 27\u201335 (1980)","journal-title":"Discrete Math."},{"issue":"2","key":"246_CR21","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0097-3165(80)90011-4","volume":"29","author":"JE Goodman","year":"1980","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)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"3","key":"246_CR22","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0097-3165(80)90038-2","volume":"29","author":"JE Goodman","year":"1980","unstructured":"Goodman, J.E., Pollack, R.: Proof of Gr\u00fcnbaum\u2019s conjecture on the stretchability of certain arrangements of pseudolines. J. Comb. Theory Ser. A 29(3), 385\u2013390 (1980)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"3","key":"246_CR23","doi-asserted-by":"crossref","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":"246_CR24","doi-asserted-by":"crossref","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. Comb. Theory Ser. A 37(3), 257\u2013293 (1984)","journal-title":"J. Comb. Theory Ser. A"},{"key":"246_CR25","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF02187696","volume":"1","author":"JE Goodman","year":"1986","unstructured":"Goodman, J.E., Pollack, R.: Upper bounds for configurations and polytopes in $$R^{{d}}$$ R d . Discrete Comput. Geom. 1, 219\u2013227 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"246_CR26","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/978-3-642-58043-7_6","volume-title":"New Trends in Discrete and Computational Geometry","author":"JE Goodman","year":"1993","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, Berlin (1993)"},{"key":"246_CR27","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$ \u03b5 -Nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"246_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-55611-7","volume-title":"Axioms and Hulls, LNCS","author":"DE Knuth","year":"1992","unstructured":"Knuth, D.E.: Axioms and Hulls, LNCS, vol. 606. Springer, Berlin (1992)"},{"key":"246_CR29","first-page":"256","volume":"78","author":"F Levi","year":"1926","unstructured":"Levi, F.: Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade. Ber. Math. Phys. Kl. S\u00e4chs. Akad. Wiss. Leipzig 78, 256\u2013267 (1926). (In German)","journal-title":"Ber. Math. Phys. Kl. S\u00e4chs. Akad. Wiss. Leipzig"},{"key":"246_CR30","doi-asserted-by":"crossref","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":"246_CR31","unstructured":"Lo, C.Y., Steiger, W.: An optimal time algorithm for ham-sandwich cuts in the plane. In: CCCG, pp. 5\u20139 (1990)"},{"key":"246_CR32","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF02187804","volume":"5","author":"J Matou\u0161ek","year":"1990","unstructured":"Matou\u0161ek, J.: Construction of $$\\varepsilon $$ \u03b5 -nets. Discrete Comput. Geom. 5, 427\u2013448 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"246_CR33","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":"246_CR34","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/978-3-642-58043-7_4","volume-title":"New Trends in Discrete and Computational Geometry","author":"J Matou\u0161ek","year":"1993","unstructured":"Matou\u0161ek, J.: Epsilon-nets and computational geometry. In: Pach, J. (ed.) New Trends in Discrete and Computational Geometry, pp. 69\u201389. Springer, Berlin (1993)"},{"issue":"2","key":"246_CR35","doi-asserted-by":"crossref","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. Syst. Sci. 50(2), 203\u2013208 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"246_CR36","doi-asserted-by":"crossref","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":"246_CR37","doi-asserted-by":"crossref","unstructured":"Meikle, L.I., Fleuriot, J.D.: Mechanical theorem proving in computational geometry. In: Hong, H., Wang, D. (eds.) Automated Deduction in Geometry. LNCS, vol. 3763, pp. 1\u201318. Springer, Berlin (2004)","DOI":"10.1007\/11615798_1"},{"key":"246_CR38","doi-asserted-by":"crossref","unstructured":"Mn\u00ebv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytope varieties. In: Viro, O.Y. (ed.) Topology and Geometry\u2014Rohlin Seminar. Lecture Notes Math., vol. 1346, pp. 527\u2013544. Springer, Berlin (1988)","DOI":"10.1007\/BFb0082792"},{"key":"246_CR39","doi-asserted-by":"crossref","unstructured":"Pichardie, D., Bertot, Y.: Formalizing convex hull algorithms. In: Boulton, R.J., Jackson, P.B. (eds.) TPHOLs, LNCS, vol. 2152, pp. 346\u2013361. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44755-5_24"},{"key":"246_CR40","unstructured":"Pilz, A.: On the complexity of problems on order types and geometric graphs. Ph.D. Thesis, Graz University of Technology (2014)"},{"key":"246_CR41","first-page":"129","volume-title":"Handbook of Discrete and Computational Geometry","author":"J Richter-Gebert","year":"2004","unstructured":"Richter-Gebert, J., Ziegler, G.M.: Oriented matroids. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn, pp. 129\u2013151. Chapman and Hall\/CRC, Boca Raton (2004)","edition":"2"},{"issue":"1","key":"246_CR42","doi-asserted-by":"crossref","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\u2013Ulam theorem. Graphs Comb. 23(1), 331\u2013341 (2007)","journal-title":"Graphs Comb."},{"key":"246_CR43","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) Graph Drawing, LNCS, vol. 5849, pp. 334\u2013344. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"246_CR44","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":"246_CR45","doi-asserted-by":"crossref","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)","DOI":"10.1137\/1116025"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0246-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0246-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0246-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T21:15:10Z","timestamp":1568582110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0246-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,28]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["246"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0246-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,11,28]]}}}