Triangulace s minimální hmotností - Minimum-weight triangulation

v výpočetní geometrie a počítačová věda, triangulace s minimální hmotností problém je problém najít a triangulace minimální celkové délky hrany.[1] To znamená vstupní polygon nebo konvexní obal sady vstupních bodů musí být rozděleny na trojúhelníky, které se setkávají od okraje k okraji a vrchol od vrcholu, a to takovým způsobem, aby se minimalizoval součet obvodů trojúhelníků. Problém je NP-tvrdé pro vstupy množiny bodů, ale lze je přiblížit libovolnému požadovanému stupni přesnosti. U polygonových vstupů to lze vyřešit přesně v polynomiálním čase. Triangulace minimální hmotnosti byla také někdy nazývána optimální triangulace.
Dějiny
Problém triangulace s minimální hmotností množiny bodů představoval Düppe a Gottschalk (1970), který navrhl jeho aplikaci na stavbu trojúhelníková nepravidelná síť modely souřadnic země a používaly a chamtivý heurista přiblížit to. Shamos & Hoey (1975) domníval se, že triangulace minimální hmotnosti se vždy shodovala s Delaunayova triangulace, ale to bylo rychle vyvráceno Lloyd (1977), a vskutku Kirkpatrick (1980) ukázaly, že váhy dvou triangulací se mohou lišit o lineární faktor.[2]
Problém s triangulací minimální hmotnosti se stal notoricky známým Garey & Johnson (1979) zahrnuli do seznamu otevřených problémů ve své knize o NP-úplnost, a mnoho následných autorů na něm zveřejnilo dílčí výsledky. Konečně, Mulzer & Rote (2008) ukázal, že je to NP-tvrdé, a Remy & Steger (2009) ukázal, že přesné aproximace lze efektivně sestavit.
Složitost
Váha triangulace sady bodů v Euklidovské letadlo je definován jako součet délek jeho hran. Své varianta rozhodnutí je problém rozhodnout, zda existuje triangulace hmotnosti menší než daná hmotnost; bylo prokázáno, že je NP-tvrdé podle Mulzer & Rote (2008). Jejich důkaz je snížení z PLANAR-1-IN-3-SAT, speciální případ Booleovský problém uspokojivosti ve kterém a 3-CNF jehož graf je rovinný je přijato, když má přiřazení pravdy, které přesně splňuje jeden literál v každé klauzuli. Důkaz je složitý gadgety a zahrnuje počítačová pomoc k ověření správného chování těchto gadgetů.
Není známo, zda je problém s rozhodováním o minimální váze triangulace NP-kompletní, protože to závisí na známém otevřeném problému, zda součet radikálů lze vypočítat v polynomiálním čase. Mulzer a Rote však poznamenávají, že problém je NP-úplný, pokud jsou okrajové váhy zaokrouhleny na celočíselné hodnoty.
Ačkoli je NP-tvrdý, může být triangulace minimální hmotnosti konstruována v subexponenciálním čase pomocí a dynamické programování algoritmus, který zohledňuje vše možné jednoduché oddělovače cyklu z body v rámci triangulace, rekurzivně najde optimální triangulaci na každé straně cyklu a zvolí oddělovač cyklu vedoucí k nejmenší celkové hmotnosti. Celková doba pro tuto metodu je .[3]
Přiblížení
Několik autorů prokázalo výsledky týkající se triangulace minimální hmotnosti s jinými triangulacemi ve smyslu přibližný poměr, nejhorší poměr celkové délky hrany alternativní triangulace k celkové délce triangulace s minimální hmotností. V tomto duchu je známo, že Delaunayova triangulace má poměr přiblížení ,[4] a to chamtivá triangulace (triangulace vytvořená přidáním hran v pořadí od nejkratší po nejdelší, v každém kroku včetně hrany, kdykoli nepřekročí dřívější hranu) má přibližný poměr .[5] Nicméně pro náhodně rozložené množiny bodů jsou Delaunayova i chamtivá triangulace v logaritmickém faktoru minimální váhy.[6]
Výsledek tvrdosti Mulzera a Roteho také implikuje NP tvrdost nalezení přibližného řešení s relativní chybou aproximace nejvýše O (1 / n2). Tak, a plně polynomiální aproximační schéma pro triangulaci s minimální hmotností je nepravděpodobné. Kvazi-polynomiální aproximační schéma je však možné: pro libovolnou konstantu ε> 0 lze řešení s aproximačním poměrem 1 + ε nalézt v kvazi-polynomiální čas exp (O ((logn)9).[7]
Heuristika
Kvůli obtížnosti najít přesná řešení triangulace s minimální hmotností mnoho autorů studovalo heuristiku, která může v některých případech najít řešení, i když nelze prokázat, že fungují ve všech případech. Velká část tohoto výzkumu se zejména zaměřila na problém hledání sad hran, u kterých je zaručeno, že patří do triangulace s minimální hmotností. Pokud se ukáže, že takto nalezený podgraf triangulace s minimální hmotností je spojen, lze zbývající zbývající trojúhelníkový prostor chápat tak, že tvoří jednoduchý polygon, a celou triangulaci lze najít pomocí dynamické programování najít optimální triangulaci tohoto polygonálního prostoru. Stejný přístup k dynamickému programování lze také rozšířit v případě, že podgraf má omezený počet připojených komponent[8] a stejný přístup k nalezení připojeného grafu a následnému použití dynamického programování k vyplnění polygonálních mezer obklopujících okraje grafu byl také použit jako součást heuristiky pro hledání trojúhelníků s nízkou a ne minimální hmotností.[9]
Graf vytvořený spojením dvou bodů, kdykoli jsou si navzájem nejbližšími sousedy, je nutně podgrafem triangulace s minimální hmotností.[10] Tento graf vzájemného nejbližšího souseda je však a vhodný, a proto nikdy není připojen. Související řada výzkumů najde velké podgrafy triangulace s minimální hmotností pomocí kruhů β- kostry, geometrické grafy vytvořené zahrnutím hrany mezi dvěma body u a proti kdykoli neexistuje třetí bod w utváření úhlu uwv větší než některý parametr θ. Ukázalo se, že pro dostatečně malé hodnoty θ je takto vytvořený graf podgrafem triangulace s minimální hmotností.[11] Volba θ potřebná k zajištění toho je však menší než úhel θ = 90ª, pro který β-skeleton je vždy připojen.
Sofistikovanější techniku nazvanou LMT-skeleton navrhl Dickerson & Montague (1996). Je tvořen iteračním procesem, ve kterém jsou udržovány dvě sady hran, sada hran, o nichž je známo, že patří do triangulace s minimální hmotností, a sada hran, které jsou kandidáty, aby do ní patřily. Zpočátku je sada známých hran inicializována na konvexní obal vstupu a všechny zbývající páry vrcholů tvoří kandidátské hrany. Poté se v každé iteraci stavebního procesu odstraní kandidátské hrany, kdykoli ze zbývajících hran není vytvořena dvojice trojúhelníků tvořících čtyřúhelník, pro který je kandidátská hrana nejkratší úhlopříčkou, a kandidátské hrany jsou přesunuty do sady známých hran když není žádná další hrana kandidáta, která by je překročila. Kostra LMT je definována jako sada známých hran vytvořených poté, co tento proces přestane provádět další změny. Je zaručeno, že se jedná o podgraf triangulace s minimální hmotností, lze ji konstruovat efektivně a při experimentech na sadách až do 200 bodů to bylo často spojeno.[12] Ukázalo se však, že v průměru pro velké množiny bodů má lineární počet připojených komponent.[13]
Mezi další heuristiky, které byly aplikovány na problém s triangulací minimální hmotnosti, patří genetické algoritmy[14] větev a svázaný,[15] a algoritmy optimalizace kolonií mravenců.[16]
Variace
A polygon triangulace o minimální hmotnosti lze sestavit za kubický čas pomocí dynamické programování přístup, nezávislý reportér Gilbert (1979) a Klincsek (1980). V této metodě jsou vrcholy číslovány postupně kolem hranice mnohoúhelníku a pro každou úhlopříčku z vrcholu i na vrchol j která leží v polygonu, optimální triangulace se vypočítá s ohledem na všechny možné trojúhelníky ijk v polygonu, přidáním vah optimálních triangulací pod úhlopříčky ik a jka výběr vrcholu k což vede k minimální celkové hmotnosti. To znamená, že pokud MWT (i,j) označuje váhu triangulace minimální hmotnosti mnohoúhelníku pod okrajem ij, pak celkový algoritmus provede následující kroky:
- Pro každou možnou hodnotu i, z n - 1 až 1, proveďte:
- Pro každou možnou hodnotu j, z i + 1 až n, dělat:
- Li ij je hrana mnohoúhelníku, nastavená MWT (i,j) = délka (ij)
- Jinak pokud ij není vnitřní úhlopříčka mnohoúhelníku, nastavte MWT (i,j) = +∞
- Jinak sada MWT (i,j) = délka (ij) + mini < k < j MWT (i,k) + MWT (k, j)
- Pro každou možnou hodnotu j, z i + 1 až n, dělat:
Po dokončení této iterace bude MWT (1,n) uloží celkovou hmotnost triangulace s minimální hmotností. Samotnou triangulaci lze získat rekurzivním prohledáváním tohoto pole, počínaje MWT (1,n), v každém kroku vyberte trojúhelník ijk což vede k minimální hodnotě pro MWT (i,j) a rekurzivně prohledávat MWT (i,k) a MWT (j,k).
Podobné metody dynamického programování lze také přizpůsobit vstupům množiny bodů, kde všechny kromě stálého počtu bodů leží na konvexní obal vstupu,[17] a bodové množiny, které leží na konstantním počtu vnořených konvexních polygonů nebo na konstantním počtu řádků, z nichž žádné dvě nepřekračují konvexní obal.[18]
Je také možné formulovat verzi problémů s množinou bodů nebo polygonových triangulací, do kterých je povoleno přidávat Steinerovy body, další vrcholy, aby se snížila celková délka hrany výsledných triangulací. V některých případech může být výsledná triangulace kratší než triangulace s minimální hmotností až o lineární faktor. Je možné aproximovat Steinerovu triangulaci s minimální váhou bodu nastaveného na konstantní faktor optima, ale konstantní faktor v aproximaci je velký.[19]
Související problémy, které byly také studovány, zahrnují konstrukci minimální hmotnosti pseudotriangulace[20] a charakterizace grafů triangulací s minimální hmotností.[21]
Poznámky
- ^ Průzkumy problému viz Xu (1998), Levcopoulos (2008), a De Loera, Rambau a Santos (2010).
- ^ Viz také Manacher & Zobrist (1979).
- ^ Lingas (1998).
- ^ Kirkpatrick (1980). Slabší hranice byla dána Manacher & Zobrist (1979).
- ^ Rodina příkladů dokazujících, že poměr přiblížení je byl dán Levcopoulos (1987) a odpovídající horní mez je Levcopoulos & Krznaric (1998). Stejně jako u aproximačního poměru pro Delaunayovu triangulaci byla slabší hranice dána také Manacher & Zobrist (1979).
- ^ Lingas (1986).
- ^ Remy & Steger (2009). Dřívější výsledky algoritmů aproximace v polynomiálním čase viz Plaisted & Hong (1987) (aproximace log-faktoru) a Levcopoulos & Krznaric (1998) (aproximace konstantním faktorem).
- ^ Cheng, Golin & Tsang (1995).
- ^ Lingas (1987); Heath & Pemmaraju (1994).
- ^ Yang, Xu & You (1994).
- ^ Keil (1994); Cheng, Golin & Tsang (1995); Cheng & Xu (2001); Hu (2010).
- ^ Dickerson & Montague (1996); Cheng, Katoh & Sugai (1996); Beirouti & Snoeyink (1998); Aichholzer, Aurenhammer & Hainz (1999).
- ^ Bose, Devroye a Evans (1996).
- ^ Qin, Wang & Gong (1997); Capp & Julstrom (1998).
- ^ Kyoda a kol. (1997).
- ^ Jahani, Bigham & Askari (2010).
- ^ Hoffmann a Okamoto (2004); Grantson, Borgelt a Levcopoulos (2005); Knauer & Spillner (2006).
- ^ Anagnostou & Corneil (1993); Meijer & Rappaport (1992).
- ^ Eppstein (1994).
- ^ Gudmundsson a Levcopoulos (2007); Aichholzer a kol. (2009).
- ^ Lenhart & Liotta (2002).
Reference
- Aichholzer, Oswin; Aurenhammer, Franz; Hackl, Thomas; Speckmann, Bettina (2009), „O pseudo-triangulacích s minimální hmotností“, Teorie a aplikace výpočetní geometrie, 42 (6–7): 627–631, doi:10.1016 / j.comgeo.2008.10.002, PAN 2519380.
- Aichholzer, Oswin; Aurenhammer, Franz; Hainz, Reinhard (1999), „New results on MWT subgraphs“, Dopisy o zpracování informací, 69 (5): 215–219, doi:10.1016 / S0020-0190 (99) 00018-6.
- Anagnostou, Efthymios; Corneil, Derek (1993), „Polynomiálně-časové instance problému s triangulací minimální hmotnosti“, Výpočetní geometrie. Teorie a aplikace, 3 (5): 247–259, doi:10.1016 / 0925-7721 (93) 90016-Y, PAN 1251594.
- Beirouti, Ronald; Snoeyink, Jack (1998), „Implementace LMT heuristiky pro triangulaci s minimální hmotností“, Proc. 14. ACM Symposium on Computational Geometry, str. 96–105, doi:10.1145/276884.276895.
- Bose, Prosenjit; Devroye, Luc; Evans, William (1996), „Diamanty nejsou nejlepším přítelem triangulace s minimální hmotností“, Proc. 8. kanadská konference o výpočetní geometrii (CCCG 1996) (PDF), s. 68–73.
- Capp, Kerry; Julstrom, Bryant A. (1998), „Váhový kódovaný genetický algoritmus pro problém s triangulací minimální hmotnosti“, Proc. ACM Symposium on Applied Computing, Atlanta, Georgia, USA, str. 327–331, doi:10.1145/330560.330833, Sémantický učenec.
- Cheng, Siu-Wing; Golin, Mordechaj; Tsang, J. (1995), „Očekávaná analýza případů β-kostry s aplikacemi na konstrukci trojúhelníků s minimální hmotností ", Proc. 7. kanadská konference o výpočetní geometrii (CCCG 1995), str. 279–284.
- Cheng, Siu-Wing; Katoh, Naoki; Sugai, Manabu (1996), „Studie kostry LMT“, Algoritmy a výpočet, Přednášky v informatice, 1178, str. 256–265, doi:10.1007 / BFb0009502.
- Cheng, Siu-Wing; Xu, Yin-Feng (2001), „On β-skelet jako podgraf triangulace minimální hmotnosti ", Teoretická informatika, 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 Chamtivost a triangulace s minimální hmotností“, Triangulace: Struktury pro algoritmy a aplikaceAlgoritmy a výpočty v matematice, 25, Springer, str. 102–107, ISBN 978-3-642-12970-4.
- Dickerson, Matthew T.; Montague, Mark H. (1996), „A (obvykle?) Připojený podgraf triangulace minimální hmotnosti“, Proc. 12. 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. Jak uvádí Mulzer & Rote (2008) a Remy & Steger (2009).
- Eppstein, David (1994), „Přibližná Steinerova triangulace minimální hmotnosti“ (PDF), Diskrétní a výpočetní geometrie, 11 (2): 163–191, doi:10.1007 / BF02574002, PAN 1254088.
- Garey, M. R.; Johnson, D. S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, San Francisco, Kalifornie: W. H. Freeman, Problém OPEN12, s. 288, ISBN 0-7167-1045-5, PAN 0519066.
- Gilbert, P. D. (1979), Nové výsledky v rovinných triangulacíchZpráva R-850, Urbana, Illinois: Coordinated Science Laboratory, University of Illinois.
- Grantson, M .; Borgelt, C .; Levcopoulos, C. (2005), „Triangulace minimální hmotnosti vyříznutím trojúhelníků“, Proc. 16. mezinárodní symposium o algoritmech a výpočtech, str. 984–994.
- Gudmundsson, Joachim; Levcopoulos, Christos (2007), „Pseudo-triangulace s minimální hmotností“, Teorie a aplikace výpočetní geometrie, 38 (3): 139–153, doi:10.1016 / j.comgeo.2007.05.004, PAN 2352529.
- Heath, L. S .; Pemmaraju, S. V. (1994), "Nové výsledky pro problém s triangulací minimální hmotnosti", Algorithmica, 12 (6): 533–552, doi:10.1007 / BF01188718, PAN 1297812.
- Hoffmann, M .; Okamoto, Y. (2004), „Problém triangulace minimální hmotnosti s několika vnitřními body“, Proc. 1. mezinárodní workshop o parametrizovaném a přesném výpočtu, str. 200–212.
- Hu, Shiyan (2010), „Nová oblast asymetrické inkluze pro triangulaci s minimální hmotností“, Journal of Global Optimization, 46 (1): 63–73, CiteSeerX 10.1.1.377.6164, doi:10.1007 / s10898-009-9409-z, PAN 2566136.
- Jahani, M .; Bigham, B.S .; Askari, A. (2010), "Algoritmus kolonií mravenců pro triangulaci s minimální hmotností", Mezinárodní konference o výpočetní vědě a jejích aplikacích (ICCSA), str. 81–85, doi:10.1109 / ICCSA.2010.38, Sémantický učenec.
- Keil, J. Mark (1994), "Výpočet podgrafu triangulace minimální hmotnosti", Výpočetní geometrie: Teorie a aplikace, 4 (1): 18–26, doi:10.1016/0925-7721(94)90014-0.
- Kirkpatrick, David G. (1980), „Poznámka k Delaunayovi a optimálním triangulacím“, Dopisy o zpracování informací, 10 (3): 127–128, doi:10.1016/0020-0190(80)90062-9, PAN 0566856.
- Klincsek, G. T. (1980), "Minimální triangulace polygonálních domén", Annals of Discrete Mathematics, 9: 121–123, doi:10.1016 / s0167-5060 (08) 70044-x, ISBN 9780444861115.
- Knauer, Christian; Spillner, Andreas (2006), „Algoritmus s pevnými parametry pro problém s triangulací minimální hmotnosti založený na malých oddělovačích grafů“, Grafově-teoretické pojmy v informatice, Přednášky v informatice, 4271, Berlín: Springer, str. 49–57, doi:10.1007/11917496_5, PAN 2290717.
- Kyoda, Yoshiaki; Imai, Keiko; Takeuchi, Fumihiko; Tajima, Akira (1997), „Věcný přístup pro triangulaci s minimální hmotností“, Algorithms and Computation (Singapur, 1997), Přednášky v informatice, 1350, Berlín: Springer, s. 384–393, doi:10.1007/3-540-63890-3_41, PAN 1651067.
- Lenhart, William; Liotta, Giuseppe (2002), „Problém tažnosti pro triangulace s minimální hmotností“, Teoretická informatika, 270 (1–2): 261–286, doi:10.1016 / S0304-3975 (00) 00383-2, PAN 1871072.
- Levcopoulos, Christos (1987), „An Ω (√n) dolní mez pro neoptimalitu chamtivé triangulace “, Dopisy o zpracování informací, 25 (4): 247–251, doi:10.1016/0020-0190(87)90170-0, PAN 0896144.
- Levcopoulos, Christos (2008), „Triangulace s minimální hmotností“, v Kao, Ming-Yang (ed.), Encyclopedia of Algorithms, Springer, str. 546–548, ISBN 978-0-387-30770-1.
- Levcopoulos, C .; Krznaric, D. (1998), „Kvazi-chamtivé triangulace přibližující triangulaci minimální hmotnosti“ (PDF), Journal of Algorithms, 27 (2): 303–338, doi:10.1006 / jagm.1997.0918, PAN 1622398.
- Lingas, Andrzej (1986), „The Greedy and Delaunay triangulation are not bad in the average case“, Dopisy o zpracování informací, 22 (1): 25–31, doi:10.1016/0020-0190(86)90038-4.
- Lingas, Andrzej (1987), „Nová heuristika pro triangulaci s minimální hmotností“, SIAM Journal o algebraických a diskrétních metodách, 8 (4): 646–658, doi:10.1137/0608053, PAN 0918066.
- Lingas, Andrzej (1998), „Algoritmy subexponenciálního času pro triangulace s minimální hmotností a související problémy“, Sborník příspěvků z 10. kanadské konference o výpočetní geometrii (CCCG'98).
- Lloyd, E. (1977), „O triangulacích množiny bodů v rovině“, Proc. 18. IEEE Symposium on Foundations of Computer Science, str. 228–240.
- Manacher, Glenn K .; Zobrist, Albert L. (1979), „Ani chamtivá, ani Delaunayova triangulace rovinné množiny bodů se nepřibližuje optimální triangulaci“, Dopisy o zpracování informací, 9 (1): 31–34, doi:10.1016/0020-0190(79)90104-2, PAN 0537055.
- Meijer, Henk; Rappaport, David (1992), „Výpočet triangulace minimální hmotnosti sady lineárně uspořádaných bodů“, Dopisy o zpracování informací, 42 (1): 35–38, doi:10.1016 / 0020-0190 (92) 90129-J, PAN 1160443.
- Mulzer, Wolfgang; Rote, Günter (2008), „Triangulace s minimální hmotností je NP-tvrdá“, Deník ACM, 55 (2), článek A11, arXiv:cs.CG/0601002, doi:10.1145/1346330.1346336.
- Plaisted, D. A .; Hong, J. (1987), „Heuristický triangulační algoritmus“, Journal of Algorithms, 8 (3): 405–437, doi:10.1016/0196-6774(87)90020-4.
- Qin, Kaihuai; Wang, Wenping; Gong, Minglun (1997), „Genetický algoritmus pro triangulaci minimální hmotnosti“, Mezinárodní konference IEEE o evolučních výpočtech, str. 541–546, doi:10.1109 / ICEC.1997.592370, hdl:10722/45578, Sémantický učenec.
- Remy, Jan; Steger, Angelika (2009), „Kvazi-polynomiální časové aproximační schéma pro triangulaci s minimální hmotností“, Deník ACM, 56 (3), článek A15, doi:10.1145/1516512.1516517.
- Shamos, M. I.; Hoey, D. J. (1975), "Problémy nejbližšího bodu", Proc. 16. IEEE Symposium on Foundations of Computer Science (PDF), s. 151–162.
- Wang, Cao An; Yang, Boting (2001), „Dolní mez pro β-skelet patřící do triangulací minimální hmotnosti ", Výpočetní geometrie: Teorie a aplikace, 19 (1): 35–46, doi:10.1016 / S0925-7721 (01) 00008-6.
- Xu, Yin-Feng (1998), „Triangulace minimální hmotnosti“, Handbook of Combinatorial Optimization, Vol. 2, Boston, MA: Kluwer Academic Publishers, s. 617–634, PAN 1665412.
- Yang, Bo Ting; Xu, Yin Feng; Vy, Zhao Yong (1994), „Algoritmus řetězového rozkladu pro důkaz vlastnosti o triangulacích s minimální hmotností“, Du, Ding-Zhu; Zhang, Xiang-Sun (eds.), Algoritmy a výpočet: 5. mezinárodní sympozium, ISAAC '94, Peking, Čína, 25. – 27. Srpna 1994, sborník, Přednášky v informatice, 834, Berlín: Springer, s. 423–427, doi:10.1007/3-540-58325-4_207, PAN 1316441.