{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:45Z","timestamp":1774421325732,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T00:00:00Z","timestamp":1752105600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T00:00:00Z","timestamp":1752105600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"name":"Tokai University, Isehara Campus"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s00224-025-10228-9","type":"journal-article","created":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T10:17:07Z","timestamp":1752142627000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Optimal and Practical Algorithm for the Planar 2-center Problem"],"prefix":"10.1007","volume":"69","author":[{"given":"Xuehou","family":"Tan","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,10]]},"reference":[{"key":"10228_CR1","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1016\/j.comgeo.2012.11.005","volume":"46","author":"PK Agarwal","year":"2013","unstructured":"Agarwal, P.K., Avraham, R.B., Sharir, M.: The 2-center problem in three dimensions. Comput. Geometry: Theory Appl. 46, 734\u2013746 (2013)","journal-title":"Comput. Geometry: Theory Appl."},{"key":"10228_CR2","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1137\/S0097539795295936","volume":"29","author":"PK Agarwal","year":"2000","unstructured":"Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM J. Comput. 29, 912\u2013953 (2000)","journal-title":"SIAM J. Comput."},{"key":"10228_CR3","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF01182774","volume":"11","author":"PK Agarwal","year":"1994","unstructured":"Agarwal, P.K., Sharir, M.: Planar geometric location problems. Algorithmica 11, 185\u2013195 (1994)","journal-title":"Algorithmica"},{"key":"10228_CR4","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. Geometry 4, 591\u2013604 (1989)","journal-title":"Discrete Comput. Geometry"},{"key":"10228_CR5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0925-7721(99)00019-X","volume":"13","author":"TM Chan","year":"1999","unstructured":"Chan, T.M.: More planar two-center algorithms. Comput. Geometry: Theory and Appl. 13, 189\u2013198 (1999)","journal-title":"Comput. Geometry: Theory and Appl."},{"key":"10228_CR6","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jagm.1996.0060","volume":"21","author":"B Chazelle","year":"1996","unstructured":"Chazelle, B., Matou\u0161ek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21, 579\u2013597 (1996)","journal-title":"J. Algorithms"},{"key":"10228_CR7","unstructured":"Cho, K., Oh, E.: Optimal algorithm for the planar two-center problem. (2020). arXiv:2007.08784"},{"key":"10228_CR8","doi-asserted-by":"publisher","first-page":"101768:1\u201310","DOI":"10.1016\/j.comgeo.2021.101768","volume":"97","author":"J Choi","year":"2021","unstructured":"Choi, J., Ahn, H.K.: Efficient planar two-center algorithms. Comput. Geometry: Theory and Appl. 97, 101768:1\u201310 (2021)","journal-title":"Comput. Geometry: Theory and Appl."},{"key":"10228_CR9","doi-asserted-by":"publisher","first-page":"101936:1\u201314","DOI":"10.1016\/j.comgeo.2022.101936","volume":"109","author":"J Choi","year":"2023","unstructured":"Choi, J., Jeong, D., Ahn, H.K.: Covering convex polygons by two congruent disks. Comput. Geometry: Theory and Appl. 109, 101936:1\u201314 (2023)","journal-title":"Comput. Geometry: Theory and Appl."},{"key":"10228_CR10","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., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer-Verlag (2008)"},{"key":"10228_CR11","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1137\/0215052","volume":"15","author":"ME Dyer","year":"1986","unstructured":"Dyer, M.E.: On a multidimensional search technique and its application to the Euclidean one-center problem. SIAM J. Comput. 15, 725\u2013738 (1986)","journal-title":"SIAM J. Comput."},{"key":"10228_CR12","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1287\/ijoc.4.4.360","volume":"4","author":"D Eppstein","year":"1992","unstructured":"Eppstein, D.: Dynamic three-dimensional linear programming. ORSA J. Comput. 4, 360\u2013368 (1992)","journal-title":"ORSA J. Comput."},{"key":"10228_CR13","unstructured":"Eppstein, D.: Faster construction of planar two-centers. In: Proc. 8th ACM-SIAM Sympos. on Discrete Algorithms, pp. 131\u2013138 (1997)"},{"key":"10228_CR14","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0020-0190(93)90153-Z","volume":"47","author":"H Hershberger","year":"1993","unstructured":"Hershberger, H.: A faster algorithm for the two-center decision problem. Inform. Process. Lett. 47, 23\u201329 (1993)","journal-title":"Inform. Process. Lett."},{"key":"10228_CR15","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/0196-6774(91)90013-O","volume":"12","author":"H Hershberger","year":"1991","unstructured":"Hershberger, H., Suri, S.: Finding tailored partitions. J. Algorithms 12, 431\u2013463 (1991)","journal-title":"J. Algorithms"},{"key":"10228_CR16","doi-asserted-by":"crossref","unstructured":"Jaromczyk, J., Kowaluk, M.: An efficient algorithm for the Euclidean two-center problem. In: Proc. 10th ACM Sympos. Comput. Geom., pp. 303\u2013311 (1994)","DOI":"10.1145\/177424.178038"},{"key":"10228_CR17","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/S0097539794268649","volume":"26","author":"MJ Katz","year":"1997","unstructured":"Katz, M.J., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Comput. 26, 1384\u20131408 (1997)","journal-title":"SIAM J. Comput."},{"key":"10228_CR18","doi-asserted-by":"publisher","unstructured":"Kim, S.K., Shin, C.S.: Efficient algorithms for the two-center problems for a convex polygon. LNCS, vol. 1858, pp. 299\u2013309. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44968-X_30","DOI":"10.1007\/3-540-44968-X_30"},{"key":"10228_CR19","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 R3\u00a0and related problems. SIAM J. Comput. 12, 759\u2013776 (1983)","journal-title":"SIAM J. Comput."},{"key":"10228_CR20","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K.: On the complexity of some common geometric location problems. SIAM J. Comput. 13, 1182\u20131196 (1984)","journal-title":"SIAM J. Comput."},{"key":"10228_CR21","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/PL00009311","volume":"18","author":"M Sharir","year":"1987","unstructured":"Sharir, M.: A near-linear time algorithm for the planar 2-center problem. Discrete Comput. Geom. 18, 125\u2013134 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"10228_CR22","doi-asserted-by":"publisher","unstructured":"Tan, X., Jiang, B.: Simple 0(n log2 n)\u00a0algorithms for the planar 2-center problem. LNCS, vol. 10392, pp. 481\u2013491. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-319-62389-4_40","DOI":"10.1007\/978-3-319-62389-4_40"},{"key":"10228_CR23","doi-asserted-by":"publisher","first-page":"1175","DOI":"10.1007\/s00454-021-00358-5","volume":"68","author":"H Wang","year":"2022","unstructured":"Wang, H.: On the planar two-center problem and circular hulls. Discrete Comput. Geom. 68, 1175\u20131226 (2022)","journal-title":"Discrete Comput. Geom."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10228-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10228-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10228-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T05:21:11Z","timestamp":1759296071000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10228-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,10]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10228"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10228-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,10]]},"assertion":[{"value":"18 June 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known completing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Completing interest"}},{"value":"The authors declare no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"29"}}