Minimalna težina triangulacije

U računarskoj geometriji i informatici, minimalna težina triangulacije je problem nalaženja triangulacije sa najmanjom ukupnom dužinom grane . To je, ulazni mnogougao ili konveksni omotač ulaznog skupa tačaka koji se mora podeliti u trouglove koji su spojeni ivica sa ivicom i teme (čvor) sa temenom, na takav način da smanje zbir obima truoglova. Problem je NP težak probem za skup ulaznih tačaka, ali se može aproksimirati do bilo koje željene preciznosti. Za ulaze mnogouglova, može se rešiti tačno u polinomijalnomvremenu. Minimalna težinska triangulacija se takođe nekad naziva kao optimalna triangulacija.

Istorija

Problem minimalne težine triangulacije skupa tačaka je postavio Düppe & Gottschalk 1970, koji je predložio zahtev za konstrukciju trougaone nepravilne mreže modela zemljišne konture, i koristi pohlepni algoritam za aproksimaciju. Shamos & Hoey 1975 je pretpostavio da se mimalna težina triangulacije uvek podudara sa Delanej triangulacijom, ali to je brzo oborio Lloyd 1977, i zapravo Kirkpatrick 1980 pokazao da težine dve triangulacije se mogu razlikovati po linearnom faktoru.

Problem minimalne težine triangulacije je postao važan kada je Garey & Johnson 1979 svrstao ovaj problem u listu nerešenih problema koji su NP-kompletni problemi, i mnogi kasniji autori su kasnije objavili parcijalne rezultate o tome. Konačno, Mulzer & Rote 2008 je pokazao da je problem NP težak problem, i Remy & Steger 2009 je pokazao da se tačna aproksimacija može efikasno napraviti.

Složenost

Težina triangulacije skupa tačaka u dvodimenzionalnom prostoru je definisana kao zbir dužina tih grana. Problem odlučivanja je problem gde se ispituje da li postoji triangulacija sa težinom manjom od date težine; dokazano je da je to NP-težak problem a dokazao ga je Mulzer & Rote 2008. Dokaz se sastoji iz smanjenja složenosti "PLANAR-1-IN-3-SAT", specijalnog slučaja SAT problema u kome Konjunktivna normalna forma čiji je graf planaran i prihvaćen je kad ima tačan zadatak koji zadovoljava tačno jedan literal u svakom uslovu. Dokaz koristi složene uređaje, i zahteva računarsku asistenciju da bi se dokazalo tačna ponašanje ovih uređaja.

Ne zna se da li je minimala težina triangulacije NP kompletan problem, pošto ovo zavisi od poznatog problema koji se pita da li se suma radikala može izračunati u polinomijalnom vremenu. Međutim, Mazler i Rout su napomenuli da je problem NP potpun problem ako su težine čvorova zaokružene na celobrojne vrednosti.

Iako je NP težak problem, može se konstruisati u podeksponencijalnom vremenu algoritmom dinamičkog programiranja, koji razmatra sve moguće jednostavne separatorske cikluse sa $O({\sqrt {n}})$ tačkama u triangulaciji, i rekurzivno nalazi optimalnu triangulaciju na svakoj strani ciklusa, i bira separatora ciklusa prema najmanjoj ukupnoj težini. Ukupno vreme ove metode je $2^{O({\sqrt {n}}\log n)}$.

Aproksimacija

Nekoliko autora je dokazalo rezultate poređenja minimalne težine triangulacije sa sa ostalim triangulacijama u smislu aproksimacije odnosa, najgori slučaj odnosa ukupne dužine grana alternativne triangulacije prema minimalnoj težini triangulacije. Poznato je da Delajnova triangulacija ima aproksimacioni odnos $\Theta (n)$, i to je pohlepna triangulacija (triangulacija formirana dodavanjem grana u poretku od najkraće do najduže, na svakom koraku uključujući granu kadgod ne prelazi raniju granu) ima aproksimacioni odnos $\Theta ({\sqrt {n}})$. Ipak, za neke nasumično isporučene skupove tačaka, obe triangulacije, i Delajnova i pohlepna triangulacija, su u logaritamskom faktoru minimalne težine.

Najteži rezultat Mazlera i Routa takođe podrazumeva NP teško pronalaženje približnog rešenja sa relativnom aproksimacionom greškom sa najviše O(1/n²). Dakle, potpuna polinomijalna aproksimacija šeme za minimalnu težinu triangulacijje je neizvesno. Međutim, kvazi-polinomijalna aproksimacija šeme je moguća: za bilo koju konstantu ε > 0, rešenje sa aproksimacionim odnosom 1 + ε se može naći u kvazi-polinomijalnom vremenu eksp (O((log n)⁹).

Heuristika

Pošto je teško naći tačna rešenja minimalne težinske triangulacije, mnogi autori su proučavaliheuristiku koja može u nekim slčajevima pronaći rešenje iako se ne može dokazati da ono radi u svim slučajevima. U nekim slučajevima, mnoga od ovih istraživanja su se fokusirala na problem nalaženja skupova grana koji su zagarantovani da pripadaju minimalnoj težinskoj triangulaciji. Ako je podgraf minimalne težinske triangulacije povezan, onda preostali netrougaoni prostor se može videti kao prostor za formiranje jednostavnog mnogougla, i cela triangulacija se može naći koristeći dinamičko programiranje kako bi se našlo optimalna triangulacija ovog mnogougaonog prostora. Isti pristup (dinamičko programiranje) se može iskoristiti za slučaj kada podgraf ima ograničen broj povezanih komponenti, i isti pristup se može koristiti za pronalaženja povezanog grafa i primenu dinamičkog programiranja (DP) da se popune rupe mnogougla (koje okružuju grane grafa), takođe se koristi kao deo heuristike za pronalazak male težine ali ne i minimalne težine triangulacije.

Graf koji nastaje povezivanjem dve tačke kad god su jedan drugom najbliži susedi, je podgraf minimalne težinske triangulacije. Međutum, ovaj najbliži susedni graf je odgovarajući, i zato nije nikad povezan. Vezana linija pretrage ponalazi najveće poodgrafove minimalne težinske triangulacije koristeći kružno bazirani β-skelete, geometrijsi grag koji nastaje uključivanjem grane između dve tačke u i v kada god ne postoji treća tačka w koja formira ugao uwv koji je veći od nekog parametra θ. Dokazano je da, za dovoljno male vrednosti θ, graf koji nastaj formiranjem na ovaj način je podgraf minimalne težinske triangulacije. Međutim, izbor θ mora obezbediti da je ovaj manji od ugla θ = 90ª za koji je β-kostur uvek povezan.

Tehnika koja je više sofisticirana se zove "LMT-kostur" koji je predložio Dickerson & Montague 1996. Formiran je iterativnim procesom, u kom dva skupa grana se održavaju, skup grana koji pripada minimalnoj težinskoj triangulaciji i skup grana koji su kandidati za pripadanje. Inicijalno, skup popznatih grana je inicijalizovan na konveksni omotač ulaza, i svi preostali parovi čvorova formiraju grane. Zatim, u svakoj iteraciji procesa konstrukcije, grane koje su kandidati se brišu kad god ne postoji par trouglova koji je formiran od preostalih grana koje formiraju četvorougao, za koji je kandidat grana najkraća dijagonala, i grane kandidati se pomeraju u skup poznatih grana kada ne postoji druge kandidat grane koja ukršta njih. "LMT-kostur" je definisan da bude skup poznatih grana koji se prouzvodi nakon što se ovaj proces završi bez ikakvih promena. Zagarantovano je da će biti podgraf minimalne težinske triangulacije, koji se može konstruisati efikasno, i u eksperimentima sa skupovima do 200 tačaka. Međutim, dokazano je da na prosečno velikim skupovima tačaka ima linearan broj povezanih komponenti.

Ostale heuristike koje su bile prihvaćene problemu minimalne težinske triangulacije uključuje genetske algoritme separacija i evaluacija, u mravlji algoritam.

Varijacije

Triangulacija mnogougla minimalne težine se može konstruisati u kubnom vremenu koristeći DP pristup, što je saopštio Gilbert 1979 i Klincsek 1980. U ovoj metodi, čvorovi su označeni brojevima uzastopno okok granice mnogougla, i za svaki dijagonalni čvor i do čvora j koji leži između mnogougla, optimalna triangulacija se izračunava uzimajući u obzir sve moguće toruglove ijk u mnogouglu, dodavanjem težine optimalne triangulacije ispod dijagonala ik i jk, i biranje čvora k koji vodi do minimalne uskupne težine. To je, ako MWT(i,j) predstavlja težinu minimalne težinske triangulacije za mnogougao ispod grane ij, onda opšti algoritam ima sledeće korake:

• Za svaku moguću vrednost i, od n − 1 sve do 1, radi:
  • Za svaku moguću vrednost j, od i + 1 do n, radi:
    • Ako je ij grana mnogougla, skup MWT(i,j) = length(ij)
    • Ako ij nije unutrašnja grana mnogougla, skup MWT(i,j) = +∞
    • Inače skup MWT(i,j) = length(ij) + min_{i < k < j} MWT(i,k) + MWT(k,j)

Posle ove završetka ove iteracije, MWT(1,n) će sadržati ukupne težine minimalne težinske triangulacije. Triangulacije se može dobiti rekurzivnom pretragom kroz niz, počevši od MWT(1,n), a na svakom koraku bira trougao ijk koji vodi do minimalne vrednosti za MWT(i,j) i rekurzivno pretražuje MWT(i,k) i MWT(j,k).

Slično DP metoda može takođe da se primeni na ulaznih skup tačaka gde sve osim konstantnog broja tačaka ležena konveksnom omotaču ulaza, i na skupu tačaka koje leže na konstantnom broju ugnežđenog konveksnog mnogougla ili na konstantnom broju linija od kojih ni jedne dve se ne ukrštaju u konveksnom omotaču.

takođe je moguće formulisati verziju skupa tačaka ili problema triangulacije mnogougla, u kome je jednoj dozvoljeno da dodaje štajnerove tačke, dodatne čvorove, u takvom poretku da smanji ukupnu dužinu grana rezultujuće triangulacije. U nekim slučajevim, rezultujuća triangulacija može biti kraća od minimalne težinske triangulacije za onoliko koliki je linearni faktor. Moguće je aproksimirati minimalnu težinu štajnerove triangulacije skupa tačaka unutar konstantnog optimalnog, ali konstantni faktor u aproksimaciji je veliki.

Srodni problem su takođe bili proučavani uključujući konstrukciju minimalne težine pseudotriangulacije ai karakteristika grafova minimalne težine triangulacije.

Reference

• Aichholzer, Oswin; Aurenhammer, Franz; Hackl, Thomas; Speckmann, Bettina (2009), „On minimum weight pseudo-triangulations”, Computational Geometry Theory and Applications, 42 (6-7): 627—631, MR 2519380, doi:10.1016/j.comgeo.2008.10.002 .
• Aichholzer, Oswin; Aurenhammer, Franz; Hainz, Reinhard (1999), „New results on MWT subgraphs”, Information Processing Letters, 69 (5): 215—219, doi:10.1016/S0020-0190(99)00018-6 .
• Anagnostou, Efthymios; Corneil, Derek (1993), „Polynomial-time instances of the minimum weight triangulation problem”, Computational Geometry. Theory and Applications, 3 (5): 247—259, MR 1251594, doi:10.1016/0925-7721(93)90016-Y .
• Beirouti, Ronald; Snoeyink, Jack (1998), „Implementations of the LMT heuristic for minimum weight triangulation”, Proc. 14th ACM Symposium on Computational Geometry, str. 96—105, doi:10.1145/276884.276895 .
• Bose, Prosenjit; Devroye, Luc; Evans, William (1996), „Diamonds are not a minimum weight triangulation's best friend”, Proc. 8th Canadian Conference on Computational Geometry (CCCG 1996) (PDF), str. 68—73 .
• Capp, Kerry; Julstrom, Bryant A. (1998), „A weight-coded genetic algorithm for the minimum weight triangulation problem”, Proc. ACM Symposium on Applied Computing, Atlanta, Georgia, United States, str. 327—331, doi:10.1145/330560.330833 .
• Cheng, Siu-Wing; Golin, Mordecai; Tsang, J. (1995), „Expected case analysis of β-skeletons with applications to the construction of minimum weight triangulations”, Proc. 7th Canadian Conference on Computational Geometry (CCCG 1995), str. 279—284 .
• Cheng, Siu-Wing; Katoh, Naoki; Sugai, Manabu (1996), „A study of the LMT-skeleton”, Algorithms and Computation, Lecture Notes in Computer Science, 1178, str. 256—265, doi:10.1007/BFb0009502 .
• Cheng, Siu-Wing; Xu, Yin-Feng (2001), „On β-skeleton as a subgraph of the minimum weight triangulation”, Theoretical Computer Science, 262 (1–2): 459—471, doi:10.1016/S0304-3975(00)00318-2 .
• De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), „3.2.3 Greedy and minimum weight triangulations”, Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, 25, Springer, str. 102—107, ISBN 978-3-642-12970-4 .
• Dickerson, Matthew T.; Montague, Mark H. (1996), „A (usually?) connected subgraph of the minimum weight triangulation”, Proc. 12th ACM Symposium on Computational Geometry, str. 204—213, doi:10.1145/237218.237364 .
• Düppe, R. D.; Gottschalk, H. J. (1970), „Automatische Interpolation von Isolinien bei willkürlich verteilten Stützpunkten”, Allgemeine Vermessungs-Nachrichten, 77: 423—426 . As cited by Mulzer & Rote 2008 and Remy & Steger 2009.
• Eppstein, David (1994), „Approximating the minimum weight Steiner triangulation” (PDF), Discrete and Computational Geometry, 11 (2): 163—191, MR 1254088, doi:10.1007/BF02574002 .
• Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, San Francisco, Calif.: W. H. Freeman, Problem OPEN12. str. 288, ISBN 978-0-7167-1045-5, MR 519066 .
• Gilbert, P. D. (1979), New results in planar triangulations, Report R-850, Urbana, Illinois: Coordinated Science Laboratory, University of Illinois .
• Grantson, M.; Borgelt, C.; Levcopoulos, C. (2005), „Minimum weight triangulation by cutting out triangles”, Proc. 16th International Symposium on Algorithms and Computation, str. 984—994 .
• Gudmundsson, Joachim; Levcopoulos, Christos (2007), „Minimum weight pseudo-triangulations”, Computational Geometry Theory and Applications, 38 (3): 139—153, MR 2352529, doi:10.1016/j.comgeo.2007.05.004 .
• Heath, L. S.; Pemmaraju, S. V. (1994), „New results for the minimum weight triangulation problem”, Algorithmica, 12 (6): 533—552, MR 1297812, doi:10.1007/BF01188718 .
• Hoffmann, M.; Okamoto, Y. (2004), „The minimum weight triangulation problem with few inner points”, Proc. 1st International Workshop on Parameterized and Exact Computation, str. 200—212 .
• Hu, Shiyan (2010), „A new asymmetric inclusion region for minimum weight triangulation”, Journal of Global Optimization, 46 (1): 63—73, MR 2566136, doi:10.1007/s10898-009-9409-z .
• Jahani, M.; Bigham, B.S.; Askari, A. (2010), „An ant colony algorithm for the minimum weight triangulation”, International Conference on Computational Science and Its Applications (ICCSA), str. 81—85, doi:10.1109/ICCSA.2010.38 .
• Keil, J. Mark (1994), „Computing a subgraph of the minimum weight triangulation” (PDF), Computational Geometry: Theory & Applications, 4 (1): 18—26, doi:10.1016/0925-7721(94)90014-0 .
• Kirkpatrick, David G. (1980), „A note on Delaunay and optimal triangulations”, Information Processing Letters, 10 (3): 127—128, MR 566856, doi:10.1016/0020-0190(80)90062-9 .
• Klincsek, G. T. (1980), „Minimal triangulations of polygonal domains”, Annals of Discrete Mathematics, 9: 121—123, doi:10.1016/s0167-5060(08)70044-x .
• Knauer, Christian; Spillner, Andreas (2006), „A fixed-parameter algorithm for the minimum weight triangulation problem based on small graph separators”, Graph-theoretic concepts in computer science, Lecture Notes in Computer Science, 4271, Berlin: Springer, str. 49—57, MR 2290717, doi:10.1007/11917496_5 .
• Kyoda, Yoshiaki; Imai, Keiko; Takeuchi, Fumihiko; Tajima, Akira (1997), „A branch-and-cut approach for minimum weight triangulation”, Algorithms and Computation (Singapore, 1997), Lecture Notes in Computer Science, 1350, Berlin: Springer, str. 384—393, MR 1651067, doi:10.1007/3-540-63890-3_41 .
• Lenhart, William; Liotta, Giuseppe (2002), „The drawability problem for minimum weight triangulations”, Theoretical Computer Science, 270 (1-2): 261—286, MR 1871072, doi:10.1016/S0304-3975(00)00383-2 .
• Levcopoulos, Christos (1987), „An Ω(√n) lower bound for the nonoptimality of the greedy triangulation”, Information Processing Letters, 25 (4): 247—251, MR 896144, doi:10.1016/0020-0190(87)90170-0 .
• Levcopoulos, Christos (2008), „Minimum Weight Triangulation”, Ur.: Kao, Ming-Yang, Encyclopedia of Algorithms, Springer, str. 546—548, ISBN 978-0-387-30770-1 .
• Levcopoulos, C.; Krznaric, D. (1998), „Quasi-greedy triangulations approximating the minimum weight triangulation” (PDF), Journal of Algorithms, 27: 303—338, MR 1622398, doi:10.1006/jagm.1997.0918 .
• Lingas, Andrzej (1986), „The Greedy and Delaunay triangulations are not bad in the average case”, Information Processing Letters, 22 (1): 25—31, doi:10.1016/0020-0190(86)90038-4 .
• Lingas, Andrzej (1987), „A new heuristic for minimum weight triangulation”, SIAM Journal on Algebraic and Discrete Methods, 8 (4): 646—658, MR 918066, doi:10.1137/0608053 .
• Lingas, Andrzej (1998), „Subexponential-time algorithms for minimum weight triangulations and related problems”, Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98) .
• Lloyd, E. (1977), „On triangulations of a set of points in the plane”, Proc. 18th IEEE Symposium on Foundations of Computer Science, str. 228—240 .
• Manacher, Glenn K.; Zobrist, Albert L. (1979), „Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation”, Information Processing Letters, 9 (1): 31—34, MR 537055, doi:10.1016/0020-0190(79)90104-2 .
• Meijer, Henk; Rappaport, David (1992), „Computing the minimum weight triangulation of a set of linearly ordered points”, Information Processing Letters, 42 (1): 35—38, MR 1160443, doi:10.1016/0020-0190(92)90129-J .
• Mulzer, Wolfgang; Rote, Günter (2008), „Minimum-weight triangulation is NP-hard”, Journal of the ACM, 55 (2), Article A11, arXiv:cs.CG/0601002 , doi:10.1145/1346330.1346336 .
• Plaisted, D. A.; Hong, J. (1987), „A heuristic triangulation algorithm”, Journal of Algorithms, 8: 405—437, doi:10.1016/0196-6774(87)90020-4 .
• Qin, Kaihuai; Wang, Wenping; Gong, Minglun (1997), „A genetic algorithm for the minimum weight triangulation”, IEEE International Conference on Evolutionary Computation, str. 541—546, doi:10.1109/ICEC.1997.592370 .
• Remy, Jan; Steger, Angelika (2009), „A quasi-polynomial time approximation scheme for minimum weight triangulation” (PDF), Journal of the ACM, 56 (3), Article A15, doi:10.1145/1516512.1516517 .
• Shamos, M. I.; Hoey, D. J. (1975), „Closest-point problems”, Proc. 16th IEEE Symposium on Foundations of Computer Science (PDF), str. 151—162 .
• Wang, Cao An; Yang, Boting (2001), „A lower bound for β-skeleton belonging to minimum weight triangulations”, Computational Geometry: Theory & Applications, 19 (1): 35—46, doi:10.1016/S0925-7721(01)00008-6 .
• Xu, Yin-Feng (1998), „Minimum weight triangulations”, Handbook of Combinatorial Optimization, Vol. 2, Boston, MA: Kluwer Academic Publishers, str. 617—634, MR 1665412 .
• Yang, Bo Ting; Xu, Yin Feng; You, Zhao Yong (1994), „A chain decomposition algorithm for the proof of a property on minimum weight triangulations”, Ur.: Du, Ding-Zhu; Zhang, Xiang-Sun, Algorithms and Computation: 5th International Symposium, ISAAC '94, Beijing, P. R. China, August 25–27, 1994, Proceedings, Lecture Notes in Computer Science, 834, Berlin: Springer, str. 423—427, MR 1316441, doi:10.1007/3-540-58325-4_207 .

Spoljašnje veze

• Minimum Weight Triangulation using an LMT Skeleton source code'