Home > Search Results: Ferko, Andrej
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.01 seconds. 
Minimum Weight Triangulation (MWT)
 Charvát, Pavel ; Kolingerová, Ivana (advisor) ; Ferko, Andrej (referee)
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...
Detailed record

See also: similar author names
4 Ferko, Alexander
Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English