Výpočet triangulace s minimální váhou (MWT)

Abstract

Pro výpočet MWT už dlouhou dobu není znám žádný polynomiální algoritmus a ani se neví, zda je NP. Tento stav zůstává podle našich zdrojů stále neznámý. V práci uvádíme přehled možných přístupů k problému, jako jsou modifikace zadání se známou složitostí nebo hledání nejrůznějších heuristik a aproximací, umožňujících v rozumném čase najít přesné nebo alespoň přibližné řešení, a porovnáváme jejich kvalitu v konkrétních situacích. Hlavní částí je popis a implementace efektivní heuristiky s (téměř?) lineární očekávanou složitostí pro rovnoměrně rozložené body v konvexní oblasti. Algoritmus modifikuje Drysdalův algoritmus hledání kandidátních hran GT a Beuroutiho výpočet modifikovaného LMT-skeletonu, u kterého navíc doplňujeme důkazy správnosti. MWT dokončíme z grafu kandidátních hran v O(n · d3 + n · d2+k), kde d je maximální stupeň vrcholu a k je největší počet vnitřních komponent nějaké stěny skeletonu. Dále navrhujeme novou aproximaci s polynomiální složitostí a (téměř?) lineární očekávanou složitostí, která se jen zřídka liší od optimální triangulace, a lze dokázat její nejhorší možný aproximační faktor O(1). Aproximace kombinuje heuristiku modifikovaného LMT-skeletonu s omezenou quasi-greedy triangulací a s triangulací minimální kostry. Minimální triangulace nakonec aplikujeme v praktickém problému výpočtu...

For a long time, it has been neither known whether MWT is solvable in a polynomial time nor whether it belongs to NP. As we now, its status still remain unknown. We present severalknown approaches to MWT such as modifications of the problem with known time complexity or various heuristics and approximations which allow us to find an exact or at least an approximate solution in a reasonable time. We compare the approximations in some particular situations. The main part of the work is devoted to a description and implementation of an efficient heuristic with (almost?) linear expected complexity for points uniformly distributed in some convex shape. The algorithm is a modification of Drysdale's algorithm for finding GT candidates and Beurouti's computation of the modified LMT-skeleton, where we add some proofs of the correctness. We are able to complete MWT from the graph of candidate edges in O(n · d3 + n · d2+k), where d is the the maximum degree and k is the maximum number of inner components of some skeleton face. Further, we suggest a new approximation of MWT with polynomial complexity in the worst case and (almost?) linear expected complexity, which only rarely differs from the optimal triangulation and has O(1) approximation factor in the worst case. This approximation combines the LMT-skeleton...