{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T06:44:46Z","timestamp":1773816286453,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540877431","type":"print"},{"value":"9783540877448","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-87744-8_6","type":"book-chapter","created":{"date-parts":[[2008,8,30]],"date-time":"2008-08-30T09:20:52Z","timestamp":1220088052000},"page":"64-75","source":"Crossref","is-referenced-by-count":7,"title":["An Efficient Algorithm for 2D Euclidean 2-Center with Outliers"],"prefix":"10.1007","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[]},{"given":"Jeff M.","family":"Phillips","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF01293483","volume":"13","author":"P.K. Agarwal","year":"1995","unstructured":"Agarwal, P.K., Matou\u0161ek, J.: Dynamic half-space range reporting and its applications. Algorithmica\u00a013, 325\u2013345 (1995)","journal-title":"Algorithmica"},{"key":"6_CR2","unstructured":"Agarwal, P.K., Phillips, J.M.: An efficient algorithm for 2D Euclidean 2-center with outliers (2008) arXiV:0806.4326"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF01182774","volume":"11","author":"P.K. Agarwal","year":"1994","unstructured":"Agarwal, P.K., Sharir, M.: Planar geometric locations problems. Algorithmica\u00a011, 185\u2013195 (1994)","journal-title":"Algorithmica"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1145\/299917.299918","volume":"30","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. ACM Computing Surveys\u00a030, 412\u2013458 (1998)","journal-title":"ACM Computing Surveys"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1989","unstructured":"Aggarwal, A., Guibas, L.J., Saxe, J., Shor, P.W.: A linear-time algorithm for computing the voronoi diagram of a convex polygon. Discrete Comput. Geom.\u00a04, 591\u2013604 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"6_CR6","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0925-7721(99)00019-X","volume":"13","author":"T. Chan","year":"1999","unstructured":"Chan, T.: More planar two-center algorithms. Comput. Geom.: Theory Apps.\u00a013, 189\u2013198 (1999)","journal-title":"Comput. Geom.: Theory Apps."},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1137\/S0097539703439404","volume":"34","author":"T. Chan","year":"2005","unstructured":"Chan, T.: Low-dimensional linear programming with violations. SIAM J. Comput.\u00a034, 879\u2013893 (2005)","journal-title":"SIAM J. Comput."},{"key":"6_CR8","unstructured":"Chan, T.: On the bichromatic k-set problem. In: Proc. 19th Annu. ACM-SIAM Sympos. Discrete Algs., pp. 561\u2013570 (2007)"},{"key":"6_CR9","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for faciity location problems with outliers. In: 12th Annu. ACM-SIAM Sympos. on Discrete Algs., pp. 642\u2013651 (2001)"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF02573988","volume":"10","author":"K.L. Clarkson","year":"1993","unstructured":"Clarkson, K.L.: A bound on local minima of arrangements that implies the upper bound theorem. Discrete Comput. Geom.\u00a010, 427\u2013433 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in geometry, II. Discrete Comput. Geom.\u00a04, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R. Cole","year":"1987","unstructured":"Cole, R.: Slowing down sorting networks to obtain faster sorting algorithms. Journal of ACM\u00a034, 200\u2013208 (1987)","journal-title":"Journal of ACM"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"T.K. Dey","year":"1998","unstructured":"Dey, T.K.: Improved bounds for planar k-sets and related problems. Discrete Comput. Geom.\u00a019, 373\u2013382 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"6_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56082-8","volume-title":"Facility Location: Applications and Theory","author":"Z. Drezner","year":"2002","unstructured":"Drezner, Z., Hamacher, H.: Facility Location: Applications and Theory. Springer, Heidelberg (2002)"},{"key":"6_CR15","unstructured":"Eppstein, D.: Faster construction of planar two-centers. In: Proc. 8th Annu. ACM-SIAM Sympos. on Discrete Algs., pp. 131\u2013138 (1997)"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G.N. Frederickson","year":"1982","unstructured":"Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in x\u2009+\u2009y and matrices with sorted columns. J. Comput. Syst. Sci.\u00a024, 197\u2013208 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR17","unstructured":"Gusfield, D.: Bounds for the parametric minimum spanning tree problem. In: Humboldt Conf. on Graph Theory, Combinatorics Comput., pp. 173\u2013183. Utilitas Mathematica (1979)"},{"key":"6_CR18","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company (1995)"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02570713","volume":"14","author":"J. Matou\u0161ek","year":"1995","unstructured":"Matou\u0161ek, J.: On geometric optimization with few violated constraints. Discrete Comput. Geom.\u00a014, 365\u2013384 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"6_CR20","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J. Matou\u0161ek","year":"1996","unstructured":"Matou\u0161ek, J., Welzl, E., Sharir, M.: A subexponential bound for linear programming and related problems. Algorithmica\u00a016, 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N.: Linear-time algorithms for linear programming in \u211d3 and related problems. SIAM J. Comput.\u00a012, 759\u2013776 (1983)","journal-title":"SIAM J. Comput."},{"key":"6_CR22","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N., Supowit, K.J.: On the complexity of some common geometric location problems. SIAM J. Comput.\u00a012, 759\u2013776 (1983)","journal-title":"SIAM J. Comput."},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/BF02574706","volume":"6","author":"M. Sharir","year":"1991","unstructured":"Sharir, M.: On k-sets in arrangement of curves and surfaces. Discrete Comput. Geom.\u00a06, 593\u2013613 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"6_CR24","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/PL00009311","volume":"18","author":"M. Sharir","year":"1997","unstructured":"Sharir, M.: A near-linear time algorithm for the planar 2-center problem. Discrete Comput. Geom.\u00a018, 125\u2013134 (1997)","journal-title":"Discrete Comput. Geom."},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Sharir, M., Welzl, E.: Rectilinear and polygonal p-piercing and p-center problems. In: Proc. 12th Annu. Sympos. Comput. Geom., pp. 122\u2013132 (1996)","DOI":"10.1145\/237218.237255"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87744-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T05:20:29Z","timestamp":1715059229000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-87744-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540877431","9783540877448"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87744-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}