{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:12:15Z","timestamp":1725455535095},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540620488"},{"type":"electronic","value":"9783540496335"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0009480","type":"book-chapter","created":{"date-parts":[[2005,10,20]],"date-time":"2005-10-20T10:32:17Z","timestamp":1129804337000},"page":"45-54","source":"Crossref","is-referenced-by-count":0,"title":["Optimal line bipartitions of point sets"],"prefix":"10.1007","author":[{"given":"Olivier","family":"Devillers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,10,11]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF01182774","volume":"11","author":"P. K. Agarwal","year":"1994","unstructured":"Pankaj K. Agarwal and M. Sharir. Planar geometric location problems. Algorithmica, 11:185\u2013195, 1994.","journal-title":"Algorithmica"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Te. Asano, B. Bhattacharya, J. M. Keil, and F. Yao. Clustering algorithms based on minimum and maximum spanning trees. In Proc. 4th Annu. ACM Sympos. Comput. Geom., pages 252\u2013257, 1988.","DOI":"10.1145\/73393.73419"},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02187699","volume":"1","author":"D. Avis","year":"1986","unstructured":"D. Avis. Diameter partitioning. Discrete Comput. Geom., 1:265\u2013276, 1986.","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"5_CR4","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"K. L. Clarkson","year":"1993","unstructured":"K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions. Comput. Geom. Theory Appl., 3(4):185\u2013212, 1993.","journal-title":"Comput. Geom. Theory Appl."},{"key":"5_CR5","volume-title":"Research Report 2871","author":"O. Devillers","year":"1996","unstructured":"O. Devillers and M. Katz. Optimal line bipartitions of point sets. Research Report 2871, INRIA, BP93, 06902 Sophia-Antipolis, France, 1996. http:\/\/www.inria.fr\/rapports\/sophia\/rr-2871.html."},{"key":"5_CR6","unstructured":"A. Glozman, K. Kedem, and G. Shpitalnik. Finding optimal bipartitions of points, 1994. manuscript."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Alex Glozman, Klara Kedem, and Gregory Shpitalnik. On some geometric selection and optimization problems via sorted matrices. In Proc. 4th Workshop Algorithms Data Struct., volume 955 of Lecture Notes in Computer Science, pages 26\u201337. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60220-8_48"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"J. Hagauer and G. Rote. Three-clustering of points in the plane. In T. Lengauer, editor, Proc. 1st Annu. European Sympos. Algorithms (ESA '93), volume 726 of Lecture Notes in Computer Science, pages 192\u2013199. Springer-Verlag, 1993.","DOI":"10.1007\/3-540-57273-2_55"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/0196-6774(91)90013-O","volume":"12","author":"J. Hershberger","year":"1991","unstructured":"J. Hershberger and S. Suri. Finding tailored partitions. J. Algorithms, 12:431\u2013463, 1991.","journal-title":"J. Algorithms"},{"key":"5_CR10","volume-title":"Technical Report MA2-IR-95-0010","author":"F. Hurtado","year":"1995","unstructured":"F. Hurtado, M. Noy, and S. Whitesides. Finding optimal k-partitions for points in convex position. Technical Report MA2-IR-95-0010, Departament de Matem\u00e0tica Aplicada II, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain, 1995."},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"J. W. Jaromczyk and M. Kowaluk. An efficient algorithm for the Euclidean two-center problem. In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 303\u2013311, 1994.","DOI":"10.1145\/177424.178038"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"M. J. Katz. Improved algorithms in geometric optimization via expanders. In Proc. 3rd Israel Symposium on Theory of Computing and Systems, pages 78\u201387, 1995.","DOI":"10.1109\/ISTCS.1995.377043"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"M. J. Katz and M. Sharir. An expander-based approach to geometric optimization. In Proc. 9th Annu. ACM Sympos. Comput. Geom., pages 198\u2013207, 1993.","DOI":"10.1145\/160985.161137"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"J. S. B. Mitchell and E. L. Wynters. Finding optimal bipartitions of points and polygons. In Proc. 2nd Workshop Algorithms Data Struct., volume 519 of Lecture Notes in Computer Science, pages 202\u2013213. Springer-Verlag, 1991.","DOI":"10.1007\/BFb0028263"},{"key":"5_CR15","first-page":"899","volume-title":"Graph Theory, Combinatorics and Applications","author":"C. Monma","year":"1991","unstructured":"C. Monma and S. Suri. Partitioning points and graphs to minimize the maximum or the sum of diameters. In Graph Theory, Combinatorics and Applications (Proc. 6th Internat. Conf. Theory Appl. Graphs), volume 2, pages 899\u2013912, New York, NY, 1991. Wiley."},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. H. Overmars","year":"1981","unstructured":"M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23:166\u2013204, 1981.","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, NY, 1985."},{"key":"5_CR18","unstructured":"J. Rokne, S. Wang, and X. Wu. Optimal bipartitions of point sets. In Proc. 4th Canad. Conf. Comput. Geom., pages 11\u201316, 1992."},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"Micha Sharir. A near-linear algorithm for the planar 2-center problem. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 106\u2013112, 1996.","DOI":"10.1145\/237218.237251"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0009480","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T22:31:16Z","timestamp":1554157876000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0009480"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540620488","9783540496335"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0009480","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}