{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T12:20:07Z","timestamp":1772367607655,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1997,4]]},"DOI":"10.1007\/pl00009291","type":"journal-article","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T12:36:03Z","timestamp":1140179763000},"page":"243-255","source":"Crossref","is-referenced-by-count":25,"title":["Cutting dense point sets in half"],"prefix":"10.1007","volume":"17","author":[{"given":"H.","family":"Edelsbrunner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Valtr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Welzl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"170300243_CR1","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02123006","volume":"10","author":"R. Alexander","year":"1990","unstructured":"R. Alexander. Geometric methods in the study of irregularities of distribution. Combinatorica 10 (1990), 115\u2013136.","journal-title":"Combinatorica"},{"key":"170300243_CR2","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BF02187725","volume":"4","author":"N. Alon","year":"1989","unstructured":"N. Alon, M. Katchalski, and W. R. Pulleyblank. The maximum size of a convex polygon in a restricted set of points in the plane. Discrete Comput. Geom. 4 (1989), 245\u2013251.","journal-title":"Discrete Comput. Geom."},{"key":"170300243_CR3","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0012-365X(86)90004-X","volume":"60","author":"N. Alon","year":"1986","unstructured":"N. Alon and M. A. Perles. On the intersection of edges of a geometric graph by straight lines. Discrete Math. 60 (1986), 75\u201390.","journal-title":"Discrete Math."},{"key":"170300243_CR4","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/BF02574700","volume":"6","author":"B. Aronov","year":"1991","unstructured":"B. Aronov, B. Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, and R. Wenger. Points and triangles in the plane and halving planes in space. Discrete Comput. Geom. 6 (1991), 435\u2013442.","journal-title":"Discrete Comput. Geom."},{"key":"170300243_CR5","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02123008","volume":"10","author":"I. B\u00e1r\u00e1ny","year":"1990","unstructured":"I. B\u00e1r\u00e1ny, Z. F\u00fcredi, and L. Lov\u00e1sz. On the number of halving planes. Combinatorica 10 (1990), 175\u2013183.","journal-title":"Combinatorica"},{"key":"170300243_CR6","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02187685","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and F. P. Preparata. Halfspace range search: an algorithmic application of k-sets. Discrete Comput. Geom. 1 (1986), 83\u201393.","journal-title":"Discrete Comput. Geom."},{"key":"170300243_CR7","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1137\/0216005","volume":"16","author":"R. Cole","year":"1987","unstructured":"R. Cole, M. Sharir, and C. K. Yap. On it-hulls and related problems. SIAM J. Comput. 16 (1987), 61\u201377.","journal-title":"SIAM J. Comput."},{"key":"170300243_CR8","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/7529.8927","volume":"5","author":"R. L. Cook","year":"1986","unstructured":"R. L. Cook. Stochastic sampling in computer graphics. ACM Trans. Graphics 5 (1986), 51\u201372.","journal-title":"ACM Trans. Graphics"},{"key":"170300243_CR9","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02574381","volume":"12","author":"T. K. Dey","year":"1994","unstructured":"T. K. Dey and H. Edelsbrunner. Counting triangle crossings and halving planes. Discrete Comput. Geom. 12 (1994), 281\u2013289.","journal-title":"Discrete Comput. Geom."},{"key":"170300243_CR10","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0097-3165(85)90017-2","volume":"38","author":"H. Edelsbrunner","year":"1985","unstructured":"H. Edelsbrunner and E. Welzl. On the number of line separations of a finite set in the plane. J. Combin. Theory Ser. A 38 (1985), 15\u201329.","journal-title":"J. Combin. Theory Ser. A"},{"key":"170300243_CR11","doi-asserted-by":"crossref","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 (1986), 271\u2013284.","journal-title":"SIAM J. Comput."},{"key":"170300243_CR12","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/0097-3165(93)90082-J","volume":"62","author":"D. Eppstein","year":"1993","unstructured":"D. Eppstein. Improved bounds for intersecting triangles and halving planes. J. Combin. Theory Ser. A 62 (1993), 176\u2013182.","journal-title":"J. Combin. Theory Ser. A"},{"key":"170300243_CR13","doi-asserted-by":"crossref","unstructured":"P. Erd\u00f6s, L. Lov\u00e1sz, A. Simmons, and E. G. Straus. Dissection graphs of planar point sets. In A Survey of Combinatorial Theory, ed. J. N. Srivastava et al, pp. 139\u2013149, North-Holland, Amsterdam, 1973.","DOI":"10.1016\/B978-0-7204-2262-7.50018-1"},{"key":"170300243_CR14","doi-asserted-by":"crossref","unstructured":"J. E. Goodman, R. Pollack, and B. Sturmfels. Coordinate representation of order types requires exponential storage. Proc. 21st Ann. ACM Symp. on Theory of Computing, 1989, pp. 405\u2013410.","DOI":"10.1145\/73007.73046"},{"key":"170300243_CR15","first-page":"639","volume":"3","author":"J. E. Goodman","year":"1990","unstructured":"J. E. Goodman, R. Pollack, and B. Sturmfels. The intrinsic spread of a configuration in \u211dd. J. Amer. Math. Soc. 3 (1990), 639\u2013651.","journal-title":"J. Amer. Math. Soc."},{"key":"170300243_CR16","first-page":"07","volume":"14","author":"L. Lov\u00e1sz","year":"1971","unstructured":"L. Lov\u00e1sz. On the number ofhalving lines. Ann. Univ.Sci. Budapest E\u00f6tv\u00f6s Sect. Math. 14 (1971), 107\u2013108.","journal-title":"Ann. Univ.Sci. Budapest E\u00f6tv\u00f6s Sect. Math."},{"key":"170300243_CR17","doi-asserted-by":"crossref","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 planar k-sets. Discrete Comput. Geom. 7 (1992), 109\u2013123.","journal-title":"Discrete Comput. Geom."},{"key":"170300243_CR18","volume-title":"The number of 3-sets of a finite point set in the plane","author":"E. Ramos","year":"1993","unstructured":"E. Ramos. The number of 3-sets of a finite point set in the plane. Rept. UIUCDCS-R-93-1843, Department of Computer Science, University of Illinois at Urbana-Champaign, IL, 1993."},{"key":"170300243_CR19","volume-title":"Integral Geometry and Geometric Probability","author":"L. A. Santal\u00f3","year":"1976","unstructured":"L. A. Santal\u00f3. Integral Geometry and Geometric Probability. Addisonesley, Reading, MA, 1976."},{"key":"170300243_CR20","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF02187831","volume":"7","author":"P. Valtr","year":"1992","unstructured":"P. Valtr. Convex independent sets and 7-holes in restricted planar point sets. Discrete Comput. Geom. 7 (1992), 135\u2013152.","journal-title":"Discrete Comput. Geom."},{"key":"170300243_CR21","volume-title":"Planar point sets with bounded ratios of distances","author":"P. Valtr","year":"1994","unstructured":"P. Valtr. Planar point sets with bounded ratios of distances. Ph.D. thesis, Fachbereich Mathematik, Freie Universit\u00e4t Berlin, Berlin, 1994."},{"key":"170300243_CR22","doi-asserted-by":"crossref","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\u2019s problem and complexes of injective functions. J. Combin. Theory Ser. A 61 (1992), 309\u2013318.","journal-title":"J. Combin. Theory Ser. A"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/PL00009291.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/PL00009291\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/PL00009291","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T09:20:46Z","timestamp":1558516846000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/PL00009291"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["170300243"],"URL":"https:\/\/doi.org\/10.1007\/pl00009291","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}