{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:35Z","timestamp":1759638515480,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:00:00Z","timestamp":1559001600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:00:00Z","timestamp":1559001600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1421231","1217462"],"award-info":[{"award-number":["1421231","1217462"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00454-019-00103-z","type":"journal-article","created":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T20:15:07Z","timestamp":1559074507000},"page":"705-730","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On Separating Points by Lines"],"prefix":"10.1007","volume":"63","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2971-398X","authenticated-orcid":false,"given":"Mitchell","family":"Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,28]]},"reference":[{"issue":"2","key":"103_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1002\/rsa.20269","volume":"35","author":"G Ambrus","year":"2009","unstructured":"Ambrus, G., B\u00e1r\u00e1ny, I.: Longest convex chains. Random Structures Algorithms 35(2), 137\u2013162 (2009)","journal-title":"Random Structures Algorithms"},{"issue":"1\u20132","key":"103_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-011-9517-2","volume":"63","author":"PK Agarwal","year":"2012","unstructured":"Agarwal, P.K., Ezra, E., Sharir, M.: Near-linear approximation algorithms for geometric hitting sets. Algorithmica 63(1\u20132), 1\u201325 (2012)","journal-title":"Algorithmica"},{"issue":"2","key":"103_CR3","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1137\/S009753979426616X","volume":"27","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Schwarzkopf, O.: Computing many faces in arrangements of lines and segments. SIAM J. Comput. 27(2), 491\u2013505 (1998)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"103_CR4","doi-asserted-by":"publisher","first-page":"2039","DOI":"10.1137\/120890855","volume":"42","author":"PK Agarwal","year":"2013","unstructured":"Agarwal, P.K., Matou\u0161ek, J., Sharir, M.: On range searching with semialgebraic sets. II. SIAM J. Comput. 42(6), 2039\u20132062 (2013)","journal-title":"SIAM J. Comput."},{"key":"103_CR5","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Pan, J.: Near-linear algorithms for geometric hitting sets and set covers. In: Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG), pp. 271\u2013279 (2014)","DOI":"10.1145\/2582112.2582152"},{"issue":"4","key":"103_CR6","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"103_CR7","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1142\/S0218195905001865","volume":"15","author":"G C\u0103linescu","year":"2005","unstructured":"C\u0103linescu, G., Dumitrescu, A., Karloff, H.J., Wan, P.-J.: Separating points by axis-parallel lines. Internat. J. Comput. Geom. Appl. 15(6), 575\u2013590 (2005)","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"3","key":"103_CR8","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B Chazelle","year":"1990","unstructured":"Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10(3), 229\u2013249 (1990)","journal-title":"Combinatorica"},{"key":"103_CR9","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B Chazelle","year":"1989","unstructured":"Chazelle, B., Welzl, E.: Quasi-optimal range searching in space of finite vc-dimension. Discrete Comput. Geom. 4, 467\u2013489 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"103_CR10","first-page":"246","volume-title":"Lecture Notes in Computer Science","author":"Kenneth L. Clarkson","year":"1993","unstructured":"Clarkson, K.L.: Algorithms for polytope covering and approximation. In: F.K.H.A. Dehne, J.-R. Sack, N. Santoro, S. Whitesides (eds.) Proceedings of the 3rd Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 709, pp. 246\u2013252. Springer, New York (1993)"},{"issue":"2","key":"103_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1002\/rsa.10114","volume":"24","author":"K Dalal","year":"2004","unstructured":"Dalal, K.: Counting the onion. Random Structures Algorithms 24(2), 155\u2013165 (2004)","journal-title":"Random Structures Algorithms"},{"key":"103_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Santa Clara (2008)","edition":"3"},{"key":"103_CR13","unstructured":"Devillers, O., Hurtado, F., Mora, M., Seara, C.: Separating several point sets in the plane. In: Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG), pp. 81\u201384 (2001)"},{"issue":"3","key":"103_CR14","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"DP Dobkin","year":"1985","unstructured":"Dobkin, D.P., Kirkpatrick, D.G.: A linear algorithm for determining the separation of convex polyhedra. J. Algorithms 6(3), 381\u2013392 (1985)","journal-title":"J. Algorithms"},{"key":"103_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"issue":"1","key":"103_CR16","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/PL00009492","volume":"23","author":"SP Fekete","year":"2000","unstructured":"Fekete, S.P.: On simple polygonalizations with optimal area. Discrete Comput. Geom. 23(1), 73\u2013110 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"103_CR17","unstructured":"Freimer, R., Mitchell, J.S.B., Piatko, C.D.: On the complexity of shattering using arrangements. Technical Report TR\u00a091-1197, Department of Computer Science, Cornell University, Ithaca (1991)"},{"key":"103_CR18","series-title":"Mathematical Surveys and Monographs","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/173","volume-title":"Geometric Approximation Algorithms","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Boston, MA (2011)"},{"key":"103_CR19","unstructured":"Har-Peled, S.: On the expected complexity of random convex hulls. (2011). CoRR, \narXiv:1111.5340"},{"key":"103_CR20","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1137\/1.9781611975031.59","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Sariel Har-Peled","year":"2018","unstructured":"Har-Peled, S., Jones, M.: On separating points by lines. In: Czumaj, A. (ed.) Proceedings of the 29th ACM-SIAM Sympososium on Discrete Algorithms (SODA\u201919), pp. 918\u2013932. SIAM (2018)"},{"issue":"2","key":"103_CR21","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1137\/120892660","volume":"27","author":"S Har-Peled","year":"2013","unstructured":"Har-Peled, S., Lidicky, B.: Peeling the grid. SIAM J. Discret. Math. 27(2), 650\u2013655 (2013)","journal-title":"SIAM J. Discret. Math."},{"key":"103_CR22","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"5786","key":"103_CR23","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1126\/science.1127647","volume":"313","author":"G Hinton","year":"2006","unstructured":"Hinton, G., Salakhutdinov, R.: Reducing the dimensionality of data with neural networks. Science 313(5786), 504\u2013507 (2006)","journal-title":"Science"},{"key":"103_CR24","unstructured":"Kyn\u010dl, J.: Vapnik\u2013Chervonenkis dimension of lines in the plane. (2012). \nhttp:\/\/mathoverflow.net\/questions\/98412\/vapnik-chervonenkis-dimension-of-lines-in-the-plane"},{"key":"103_CR25","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. 8, 315\u2013334 (1992)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20133","key":"103_CR26","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0166-218X(01)00315-8","volume":"122","author":"SC Nandy","year":"2002","unstructured":"Nandy, S.C., Asano, T., Harayama, T.: Shattering a set of objects in 2D. Discret. Appl. Math. 122(1\u20133), 183\u2013194 (2002)","journal-title":"Discret. Appl. Math."},{"key":"103_CR27","volume-title":"Davenport\u2013Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport\u2013Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"},{"issue":"3","key":"103_CR28","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s00454-009-9225-8","volume":"44","author":"W Steiger","year":"2010","unstructured":"Steiger, W., Zhao, J.: Generalized ham-sandwich cuts. Discrete Comput. Geom. 44(3), 535\u2013545 (2010)","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00103-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00103-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00103-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T23:18:59Z","timestamp":1590535139000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00103-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,28]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["103"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00103-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2019,5,28]]},"assertion":[{"value":"23 March 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}