{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:00Z","timestamp":1759637940107},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2017,3]]},"abstract":"<jats:p> We propose an algorithm for finding a [Formula: see text]-approximate shortest path through a weighted 3D simplicial complex [Formula: see text]. The weights are integers from the range [Formula: see text] and the vertices have integral coordinates. Let [Formula: see text] be the largest vertex coordinate magnitude, and let [Formula: see text] be the number of tetrahedra in [Formula: see text]. Let [Formula: see text] be some arbitrary constant. Let [Formula: see text] be the size of the largest connected component of tetrahedra whose aspect ratios exceed [Formula: see text]. There exists a constant [Formula: see text] dependent on [Formula: see text] but independent of [Formula: see text] such that if [Formula: see text], the running time of our algorithm is polynomial in [Formula: see text], [Formula: see text] and [Formula: see text]. If [Formula: see text], the running time reduces to [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0218195917600020","type":"journal-article","created":{"date-parts":[[2017,9,14]],"date-time":"2017-09-14T06:24:13Z","timestamp":1505370253000},"page":"13-32","source":"Crossref","is-referenced-by-count":1,"title":["Navigating Weighted Regions with Scattered Skinny Tetrahedra"],"prefix":"10.1142","volume":"27","author":[{"given":"Siu-Wing","family":"Cheng","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, HKUST, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Man-Kwun","family":"Chiu","sequence":"additional","affiliation":[{"name":"National Institute of Informatics (NII), Tokyo, Japan"},{"name":"JST, ERATO, Kawarabayashi Large Graph Project, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiongxin","family":"Jin","sequence":"additional","affiliation":[{"name":"Google Inc., USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Vigneron","sequence":"additional","affiliation":[{"name":"School of Electrical and Computer Engineering, Ulsan National Institute of Science and Technology, Ulsan, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2017,9,13]]},"reference":[{"key":"S0218195917600020BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.05.001"},{"key":"S0218195917600020BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.011"},{"key":"S0218195917600020BIB004","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195911003755"},{"key":"S0218195917600020BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044733"},{"key":"S0218195917600020BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9486-0"},{"key":"S0218195917600020BIB008","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000095"},{"key":"S0218195917600020BIB009","doi-asserted-by":"publisher","DOI":"10.1137\/130913808"},{"key":"S0218195917600020BIB012","doi-asserted-by":"publisher","DOI":"10.1137\/06067777X"},{"key":"S0218195917600020BIB013","doi-asserted-by":"publisher","DOI":"10.1137\/080742166"},{"key":"S0218195917600020BIB016","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"S0218195917600020BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.cageo.2012.12.005"},{"key":"S0218195917600020BIB018","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797325223"},{"key":"S0218195917600020BIB019","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"S0218195917600020BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009323"},{"key":"S0218195917600020BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0027-5"},{"key":"S0218195917600020BIB024","volume-title":"Geophysical Data Analysis: Discrete Inverse Theory","author":"Menke W.","year":"2012"},{"key":"S0218195917600020BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"key":"S0218195917600020BIB026","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"S0218195917600020BIB027","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102784"},{"key":"S0218195917600020BIB029","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90029-8"},{"key":"S0218195917600020BIB030","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1998"},{"key":"S0218195917600020BIB031","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9031-0"},{"key":"S0218195917600020BIB032","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2004.837232"},{"key":"S0218195917600020BIB033","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.004"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195917600020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:33:24Z","timestamp":1565120004000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195917600020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3]]},"references-count":24,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2017,9,13]]},"published-print":{"date-parts":[[2017,3]]}},"alternative-id":["10.1142\/S0218195917600020"],"URL":"https:\/\/doi.org\/10.1142\/s0218195917600020","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3]]}}}