{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T21:14:37Z","timestamp":1649106877765},"reference-count":0,"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":[[1997,2]]},"abstract":"<jats:p> We consider the following problem: given a planar straight-line graph, find a covering triangulation whose maximum angle is as small as possible. A covering triangulation is a triangulation whose vertex set contains the input vertex set and whose edge set contains the input edge set. The covering triangulation problem differs from the usual Steiner triangulation problem in that we may not add a vertex on any input edge. Covering triangulations provide a convenient method for triangulating multiple regions sharing a common boundary, as each region can be triangulated independently. <\/jats:p><jats:p> We give an explicit lower bound \u03b3<jats:sub>opt<\/jats:sub> on the maximum angle in any covering triangulation of a particular input graph in terms of its local geometry. Our algorithm produces a covering triangulation whose maximum angle \u03b3 is provably close to \u03b3<jats:sub>opt<\/jats:sub>. Specifically, we show that [Formula: see text], i.e., our \u03b3 is not much closer to \u03c0 than is \u03b3<jats:sub>opt<\/jats:sub>. To our knowledge, this result represents the first nontrivial bound on a covering triangulation's maximum angle. Our algorithm adds O(n) Steiner points and runs in time O(n log n), where n is the number of vertices of the input. We have implemented an O(n<jats:sup>2<\/jats:sup>) time version of our algorithm. <\/jats:p>","DOI":"10.1142\/s021819599700003x","type":"journal-article","created":{"date-parts":[[2003,10,16]],"date-time":"2003-10-16T10:47:26Z","timestamp":1066301246000},"page":"5-20","source":"Crossref","is-referenced-by-count":2,"title":["Finding a Covering Triangulation Whose Maximum Angle is  Provably Small"],"prefix":"10.1142","volume":"07","author":[{"given":"Scott A.","family":"Mitchell","sequence":"first","affiliation":[{"name":"Computational Mechanics &amp; Visualization Department, Sandia National Laboratories, MS 0441, P. O. Box 5800,  Albuquerque, New Mexico 87185-5800, U.S.A."}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819599700003X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:30:59Z","timestamp":1565137859000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021819599700003X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,2]]},"references-count":0,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1997,2]]}},"alternative-id":["10.1142\/S021819599700003X"],"URL":"https:\/\/doi.org\/10.1142\/s021819599700003x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,2]]}}}