{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T19:34:33Z","timestamp":1771961673071,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540646822","type":"print"},{"value":"9783540691068","type":"electronic"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"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":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054358","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"95-106","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Constrained square-center problems"],"prefix":"10.1007","author":[{"given":"Matthew J.","family":"Katz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klara","family":"Kedem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Segal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF01182774","volume":"11","author":"P. Agarwal","year":"1994","unstructured":"P. Agarwal and M. Sharir, \u201cPlanar geometric location problems\u201d, Algorithmica 11 (1994), 185\u2013195.","journal-title":"Algorithmica"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"P. Agarwal, M. Sharir, E. Welzl, \u201cThe discrete 2-center problem\u201d, Proc. 13th ACM Symp. on Computational Geometry, 147\u2013155, 1997.","DOI":"10.1145\/262839.262921"},{"issue":"4","key":"9_CR3","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole, \u201cParallel merge sort\u201d, SIAM J. Computing 17(4) (1988), 770\u2013785.","journal-title":"SIAM J. Computing"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. van Kreveld, M. Overmars and O. Schwartzkopf, Computational Geometry, Algorithms and Applications, Springer-Verlag, 1997.","DOI":"10.1007\/978-3-662-03427-9"},{"issue":"3","key":"9_CR5","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF02579232","volume":"2","author":"L. Danzer","year":"1982","unstructured":"L. Danzer and B. Gr\u00fcnbaum, \u201cIntersection properties of boxes in Rd\u201d, Combinatorica 2(3) (1982), 237\u2013246.","journal-title":"Combinatorica"},{"key":"9_CR6","unstructured":"O. Devillers and M. J. Katz, \u201cOptimal line bipartitions of point sets\u201d, Int. J. Comput. Geom. and Appls, to appear."},{"key":"9_CR7","unstructured":"D. Eppstein, \u201cFaster construction of planar two-centers\u201d, Proc. 8th ACM-SIAM Symp. on Discrete Algorithms, 131\u2013138, 1997."},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"G.N. Frederickson","year":"1984","unstructured":"G.N. Frederickson and D.B. Johnson, \u201cGeneralized selection and ranking: sorted matrices\u201d, SIAM J. Computing 13 (1984), 14\u201330.","journal-title":"SIAM J. Computing"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"A. Glozman, K. Kedem and G. Shpitalnik, \u201cEfficient solution of the two-line center problem and other geometric problems via sorted matrices\u201d, Proc. 4th Workshop Algorithms Data Struct., Lecture Notes in Computer Science (955), 26\u201337, 1995.","DOI":"10.1007\/3-540-60220-8_48"},{"key":"9_CR10","unstructured":"J.W. Jaromczyk and M. Kowaluk, \u201cOrientation independent covering of point sets in R2 with pairs of rectangles or optimal squares\u201d, Proc. European Workshop on Computational Geometry, Lecture Notes in Computer Science (871), 71\u201378, 1996."},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"J.W. Jaromczyk and M. Kowaluk, \u201cThe two-line center problem from a polar view: A new algorithm and data structure\u201d, Proc. 4th Workshop Algorithms Data Struct., Lecture Notes in Computer Science (955), 13\u201325, 1995.","DOI":"10.1007\/3-540-60220-8_47"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"M.J. Katz and F. Nielsen, \u201cOn piercing sets of objects\u201d, Proc. 12th ACM Symp. on Computational Geometry, 113\u2013121, 1996.","DOI":"10.1145\/237218.237253"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/S0097539794268649","volume":"26","author":"M.J. Katz","year":"1997","unstructured":"M.J. Katz and M. Sharir, \u201cAn expander-based approach to geometric optimization\u201d, SIAM J. Computing 26 (1997), 1384\u20131408.","journal-title":"SIAM J. Computing"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, \u201cApplying parallel computation algorithms in the design of serial algorithms\u201d, J. ACM 30 (1983), 852\u2013865.","journal-title":"J. ACM"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, Multi-dimensional Searching and Computational Geometry, in \u201cData Structures and Algorithms\u201d, vol. 3, Springer-Verlag, 1984.","DOI":"10.1007\/978-3-642-69900-9_2"},{"key":"9_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, \u201cMaintenance of configurations in the plane\u201d, J. Comput. Syst. Sci. 23 (1981), 166\u2013204.","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"M. Segal, \u201cOn the piercing of axis-parallel rectangles and rings\u201d, Proc. 5th European Symp. on Algorithms, Lecture Notes in Computer Science (1284), 430\u2013442, 1997.","DOI":"10.1007\/3-540-63397-9_33"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"M. Sharir, \u201cA near-linear algorithm for the planar 2-center problem\u201d, Proc. 12th ACM Symp. on Computational Geometry, 106\u2013112, 1996.","DOI":"10.1145\/237218.237251"},{"key":"9_CR19","volume-title":"Davenport-Shintzel sequences and their applications","author":"M. Sharir","year":"1995","unstructured":"M. Sharir and P. Agarwal, Davenport-Shintzel sequences and their applications, Cambridge University Press, New-York, 1995."},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"M. Sharir and E. Welzl, \u201cRectilinear and polygonal p-piercing and p-center problems\u201d, Proc. 12th ACM Symp. on Computational Geometry, 122\u2013132, 1996.","DOI":"10.1145\/237218.237255"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054358","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T19:18:11Z","timestamp":1676575091000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054358"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0054358","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"26 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}