{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T05:34:54Z","timestamp":1772516094948,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1994,4,1]],"date-time":"1994-04-01T00:00:00Z","timestamp":765158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1994,4,1]],"date-time":"1994-04-01T00:00:00Z","timestamp":765158400000},"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":["Discrete Comput Geom"],"published-print":{"date-parts":[[1994,4]]},"DOI":"10.1007\/bf02574017","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T12:08:49Z","timestamp":1174565329000},"page":"433-452","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":59,"title":["Algorithms for ham-sandwich cuts"],"prefix":"10.1007","volume":"11","author":[{"given":"Chi-Yuan","family":"Lo","sequence":"first","affiliation":[]},{"given":"J.","family":"Matou\u0161ek","sequence":"additional","affiliation":[]},{"given":"W.","family":"Steiger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1994,4,1]]},"reference":[{"key":"BF02574017_CR1","doi-asserted-by":"crossref","unstructured":"P.K. Agarwal and J. Matou\u0161ek. Dynamic half-space range reporting and its applications. Technical Report CS-91-43, Department of Computer Science, Duke University, 1991. The results combined with results of D. Eppstein appear inProc. 33rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 80\u201389.","DOI":"10.1109\/SFCS.1992.267816"},{"key":"BF02574017_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. Sorting inc Logn parallel steps.Combinatorica 3, 1\u201319, 1983.","journal-title":"Combinatorica"},{"key":"BF02574017_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1749-6632.1989.tb22429.x","volume":"555","author":"J. Akiyama","year":"1989","unstructured":"J. Akiyama and N. Alon. Disjoint simplices and geometric hypergraphs.Ann. N.Y. Acad. Sci. 555, 1\u20133, 1989.","journal-title":"Ann. N.Y. Acad. Sci."},{"key":"BF02574017_CR4","doi-asserted-by":"crossref","unstructured":"N. Alon, I. B\u00e1r\u00e1ny, Z. F\u00fcredi, and D. Kleitman. Point selections and weak \u03b5-nets for convex hulls. Manuscript, 1991.","DOI":"10.1017\/S0963548300000225"},{"key":"BF02574017_CR5","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/BF02574700","volume":"6","author":"B. Aronov","year":"1991","unstructured":"B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and R. Wenger. Points and triangles in the plane and halving planes in the space.Discrete Comput. Geom. 6, 435\u2013442, 1991.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574017_CR6","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0000(85)90065-0","volume":"3","author":"M. Atallah","year":"1985","unstructured":"M. Atallah. A matching problem in the plane.J. Comput. System. Sci. 3, 63\u201370, 1985.","journal-title":"J. Comput. System. Sci."},{"key":"BF02574017_CR7","doi-asserted-by":"crossref","unstructured":"I. B\u00e1r\u00e1ny and W. Steiger. On the expected number ofk-sets. Technical Report, Rutgers University, 1992. AlsoDiscrete Comput. Geom. 11 243\u2013263, 1994.","DOI":"10.1007\/BF02574008"},{"key":"BF02574017_CR8","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1137\/0218055","volume":"18","author":"R. Cole","year":"1989","unstructured":"R. Cole, J. S. Salowe, W. L. Steiger and E. Szemer\u00e9di. An optimal-time algorithm for slope selection.SIAM J. Comput. 18, 792\u2013810, 1989.","journal-title":"SIAM J. Comput."},{"key":"BF02574017_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1137\/0216005","volume":"16","author":"R. Cole","year":"1987","unstructured":"R. Cole, M. Sharir, and C. Yap. Onk-hulls and related topics.SIAM J. Comput. 16, 61\u201377, 1987.","journal-title":"SIAM J. Comput."},{"key":"BF02574017_CR10","doi-asserted-by":"crossref","unstructured":"T. Dey and H. Edelsbrunner. Counting simplex crossings and halving hyperplanes.Proc. 9th Annual ACM Symposium on Computational Geometry, 1993, pp. 270\u2013273.","DOI":"10.1145\/160985.161148"},{"key":"BF02574017_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0218195992000020","volume":"2","author":"M. B. Dillencourt","year":"1992","unstructured":"M. B. Dillencourt, D. M. Mount, and N. S. Netanyahu. A randomized algorithm for slope selection.Internat. J. Comput. Geom. Appl. 2, 1\u201327, 1992.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"BF02574017_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin, 1987."},{"key":"BF02574017_CR13","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF01840438","volume":"1","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner. Edge-skeletons in arrangements with applications.Algorithmica 1, 93\u2013109, 1986.","journal-title":"Algorithmica"},{"key":"BF02574017_CR14","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0747-7171(86)80020-7","volume":"2","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and R. Waupotitsch. Computing a ham sandwich cut in two dimensions.J. Symbolic Comput. 2, 171\u2013178, 1986.","journal-title":"J. Symbolic Comput."},{"key":"BF02574017_CR15","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1137\/0215019","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and E. Welzl. Constructing belts in two-dimensional arrangements with applications.SIAM J. Comput. 15, 271\u2013284, 1986.","journal-title":"SIAM J. Comput."},{"key":"BF02574017_CR16","doi-asserted-by":"crossref","unstructured":"C.-Y. Lo, J. Matou\u0161ek, and W. L. Steiger. Ham-sandwich cuts inR d.Proc. 24th ACM Symposium on Theory of Computing, 1992, pp. 539\u2013545.","DOI":"10.1145\/129712.129765"},{"key":"BF02574017_CR17","unstructured":"C.-Y. Lo and W. L. Steiger. An optimal time algorithm for ham-sandwich cuts in the plane.Proc. 2nd Canadian Conference on Computational Geometry, 1990, pp. 5\u20139."},{"key":"BF02574017_CR18","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF02187804","volume":"5","author":"J. Matou\u0161ek","year":"1990","unstructured":"J. Matou\u0161ek. Construction of \u03b5-nets.Discrete Comput. Geom. 5, 427\u2013448, 1990.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574017_CR19","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek. Approximations and optimal geometric divide-and-conquer.Proc. 23rd Annual ACM Symposium on Theory of Computing 1991, pp. 505\u2013511.","DOI":"10.1145\/103418.103470"},{"key":"BF02574017_CR20","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek. Randomized optimal algorithm for slope selection.Inform. Process. Lett., 183\u2013187, 1991.","DOI":"10.1016\/0020-0190(91)90177-J"},{"key":"BF02574017_CR21","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0196-6774(85)90011-2","volume":"6","author":"N. Megiddo","year":"1985","unstructured":"N. Megiddo. Partitioning with two lines in the plane,J. Algorithms 6, 430\u2013433, 1985.","journal-title":"J. Algorithms"},{"key":"BF02574017_CR22","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02187829","volume":"7","author":"J. Pach","year":"1992","unstructured":"J. Pach, W. Steiger, and E. Szemer\u00e9di. An upper bound on the number of planark-sets.Discrete Comput. Geom. 7, 109\u2013123, 1992.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574017_CR23","unstructured":"L. Shafer and W. Steiger. Randomizing optimal geometric algorithms.Proc. 5th Canadian Conference on Computational Geometry, 1993."},{"key":"BF02574017_CR24","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1137\/0211012","volume":"11","author":"D. Willard","year":"1982","unstructured":"D. Willard. Polygon retrieval.SIAM J. Comput. 11, 149\u2013165, 1982.","journal-title":"SIAM J. Comput."},{"key":"BF02574017_CR25","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0097-3165(92)90028-S","volume":"61","author":"R. T. \u017divaljevi\u0107","year":"1992","unstructured":"R. T. \u017divaljevi\u0107 and S. T. Vre\u0107ica. The colored Tverberg problem and complexes of injective functions.J. Combin. Theory Ser. A 61, 309\u2013318, 1992.","journal-title":"J. Combin. Theory Ser. A"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574017.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF02574017\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574017.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T04:37:01Z","timestamp":1736915821000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF02574017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["BF02574017"],"URL":"https:\/\/doi.org\/10.1007\/bf02574017","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,4]]},"assertion":[{"value":"21 September 1992","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 1993","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 1994","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}