{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T17:13:00Z","timestamp":1648919580941},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:p> Given an unknown target planar map, we present an algorithm for constructing an approximation of the unknown target based on information gathered from linear probes of the target. Our algorithm is a general purpose reconstruction algorithm that can be applied in many settings. Our algorithm is particularly suited for the setting where computing the intersection of a line with an unknown target is much simpler than computing the unknown target itself. The algorithm maintains a triangulation from which the approximation of the unknown target can be extracted. We evaluate the quality of the approximation with respect to the target both in the topological sense and the metric sense. The correctness of the algorithm and the evaluation of its time complexity are also presented. Finally, we present some experimental results. For example, since generalized Voronoi diagrams are planar maps, our algorithm presents a simpler alternative method for constructing approximations of generalized Voronoi diagrams, which are notoriously difficult to compute. <\/jats:p>","DOI":"10.1142\/s0218195907002471","type":"journal-article","created":{"date-parts":[[2008,1,2]],"date-time":"2008-01-02T11:11:51Z","timestamp":1199272311000},"page":"529-554","source":"Crossref","is-referenced-by-count":0,"title":["A GENERAL APPROXIMATION ALGORITHM FOR PLANAR MAPS WITH APPLICATIONS"],"prefix":"10.1142","volume":"17","author":[{"given":"PROSENJIT","family":"BOSE","sequence":"first","affiliation":[{"name":"Carleton University, 1125 Colonel By Drive, K1S 5B6 Ottawa, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"NARC\u00cdS","family":"COLL","sequence":"additional","affiliation":[{"name":"Universitat de Girona, Campus Montilivi, Girona 17071, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FERRAN","family":"HURTADO","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, C\/ Jordi Girona 1-3, Barcelona 08034, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. ANTONI","family":"SELLAR\u00c8S","sequence":"additional","affiliation":[{"name":"Universitat de Girona, Campus Montilivi, Girona 17071, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","first-page":"686","volume":"23","author":"Aurenhammer F.","journal-title":"ACM Comput. Surv."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50006-1"},{"key":"rf3","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"Di Battista G.","year":"1999"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1028"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.019"},{"key":"rf12","volume-title":"Computational Principles of Mobile Robotics","author":"Dudek G.","year":"2000"},{"key":"rf13","volume-title":"Multiple View Geometry in Computer Vision","author":"Hartley R.","year":"2000"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1109\/38.156016"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013"},{"key":"rf18","volume-title":"Integral Geometry and Geometric Probability","author":"Santal\u00f3 L. A.","year":"1976"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970418"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(82)90057-7"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195998000114"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195907002471","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:29:54Z","timestamp":1565137794000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195907002471"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12]]},"references-count":14,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2007,12]]}},"alternative-id":["10.1142\/S0218195907002471"],"URL":"https:\/\/doi.org\/10.1142\/s0218195907002471","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12]]}}}