{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,3]],"date-time":"2023-10-03T19:18:42Z","timestamp":1696360722953},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"05n06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p> An open question in Exact Geometric Computation is whether there are transcendental computations that can be made \"geometrically exact\". Perhaps the simplest such problem in computational geometry is that of computing the shortest obstacle-avoiding path between two points p,q in the plane, where the obstacles are a collection of n discs. <\/jats:p><jats:p> This problem can be solved in O(n<jats:sup>2<\/jats:sup> log n) time in the Real RAM model, but nothing was known about its computability in the standard (Turing) model of computation. We first give a direct proof of the Turing-computability of this problem, provided the radii of the discs are rationally related. We make the usual assumption that the numerical input data are real algebraic numbers. By appealing to effective bounds from transcendental number theory, we further show a single-exponential time upper bound when the input numbers are rational. <\/jats:p><jats:p> Our result appears to be the first example of a non-algebraic combinatorial problem which is shown computable. It is also a rare example of transcendental number theory yielding positive computational results. <\/jats:p>","DOI":"10.1142\/s0218195906002191","type":"journal-article","created":{"date-parts":[[2006,11,3]],"date-time":"2006-11-03T06:57:15Z","timestamp":1162537035000},"page":"567-590","source":"Crossref","is-referenced-by-count":10,"title":["SHORTEST PATH AMIDST DISC OBSTACLES IS COMPUTABLE"],"prefix":"10.1142","volume":"16","author":[{"given":"EE-CHIEN","family":"CHANG","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SUNG WOO","family":"CHOI","sequence":"additional","affiliation":[{"name":"Duksung Women's University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DO YONG","family":"KWON","sequence":"additional","affiliation":[{"name":"Korea Institute for Advanced Study, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HYUNGJU","family":"PARK","sequence":"additional","affiliation":[{"name":"Korea Institute for Advanced Study, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHEE K.","family":"YAP","sequence":"additional","affiliation":[{"name":"Courant Institute of Mathematical Sciences, New York University, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","unstructured":"C. K.\u00a0Yap, Handbook of Discrete and Computational Geometry, 2nd edn., eds. J. E.\u00a0Goodman and J.\u00a0O'Rourke (Chapmen & Hall\/CRC, Boca Raton, FL, 2004)\u00a0pp. 927\u2013952."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-6280-4_16"},{"key":"rf6","series-title":"Encycolpaedia of Mathematical Sciences","volume-title":"Number Theory IV: Transcendental Numbers","volume":"44","author":"Fel'dman N.","year":"1998"},{"key":"rf7","volume-title":"Transcendental Number Theory","author":"Baker A.","year":"1979"},{"key":"rf8","volume-title":"Introduction to Transcendental Numbers","author":"Lang S.","year":"1996"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1997.0157"},{"key":"rf10","author":"Richardson D.","journal-title":"Comput. Geometry: Theory and Appl."},{"key":"rf11","volume-title":"Fundamental Problems of Algorithmic Algebra","author":"Yap C. K.","year":"2000"},{"key":"rf12","volume-title":"Complexity and Real Computation","author":"Blum L.","year":"1988"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1142\/9789812794833_0012"},{"key":"rf17","volume-title":"Numerical Analysis: Mathematics of Scientific Computing","author":"Kincaid D.","year":"2002"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700021431"},{"key":"rf19","doi-asserted-by":"crossref","first-page":"257","DOI":"10.4064\/aa-37-1-257-283","volume":"37","author":"Waldschmidt M.","journal-title":"Acta Arith."},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009463"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195906002191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:22:16Z","timestamp":1565176936000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195906002191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":15,"journal-issue":{"issue":"05n06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1142\/S0218195906002191"],"URL":"https:\/\/doi.org\/10.1142\/s0218195906002191","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]}}}