{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T16:08:10Z","timestamp":1707581290382},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p> We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n \u2013 k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, for a total of n vertices. All four algorithms rely on the same abstract divide-and-conquer scheme, which is made efficient by a variant of dynamic programming. They are essentially based on two simple observations about triangulations, which give rise to triangle splits and paths splits. While each of the first two algorithms uses only one of these split types, the last two algorithms combine them in order to achieve certain improvements and thus to reduce the time complexity. By discussing this sequence of four algorithms we try to bring out the core ideas as clearly as possible and thus strive to achieve a deeper understanding as well as a simpler specification of these approaches. In addition, we implemented all four algorithms in Java and report results of experiments we carried out with this implementation. <\/jats:p>","DOI":"10.1142\/s0218195908002581","type":"journal-article","created":{"date-parts":[[2008,6,19]],"date-time":"2008-06-19T04:12:32Z","timestamp":1213848752000},"page":"185-220","source":"Crossref","is-referenced-by-count":5,"title":["FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM"],"prefix":"10.1142","volume":"18","author":[{"given":"MAGDALENE GRANTSON","family":"BORGELT","sequence":"first","affiliation":[{"name":"Department of Information and Computing Sciences, PO Box 80.007, 3508 TA Utrecht, The Netherlands"}]},{"given":"CHRISTIAN","family":"BORGELT","sequence":"additional","affiliation":[{"name":"European Center for Soft Computing, c\/ Gonzalo Guti\u00e9rrez Quir\u00f3s s\/n, 33600 Mieres, Spain"}]},{"given":"CHRISTOS","family":"LEVCOPOULOS","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lund University, Box 118, 221 Lund, Sweden"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195902000979"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00318-2"},{"key":"rf7","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1989"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"rf10","volume-title":"Computers and Intractability: A Guide to Theory of NP'-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf14","doi-asserted-by":"crossref","unstructured":"L.\u00a0Heath and S.\u00a0Pemmaraju, Algorithmica\u00a012 (Springer-Verlag, New York, NY, USA, 1994)\u00a0pp. 533\u2013552.","DOI":"10.1007\/BF01188718"},{"key":"rf16","first-page":"13","volume":"4","author":"Keil J.","journal-title":"Comput. Geom."},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70044-X"},{"key":"rf18","first-page":"127","volume":"10","author":"Klincsek G. T.","journal-title":"Inform. Process. Lett."},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90170-0"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0918"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1137\/0608053"},{"key":"rf25","first-page":"211","volume":"2","author":"Lodi E.","journal-title":"Fund. Inform."},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1137\/0403010"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90104-2"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759065"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90020-4"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00008-6"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195908002581","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:16:54Z","timestamp":1565176614000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195908002581"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":18,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1142\/S0218195908002581"],"URL":"https:\/\/doi.org\/10.1142\/s0218195908002581","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}