| 1. |
- Andersson, Mattias, et al.
(författare)
-
Restricted mesh simplification using edge contractions
- 2006
-
Ingår i: Computing and combinatorics / Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783540369257 ; 4112, s. 196-204
-
Konferensbidrag (refereegranskat)abstract
- We consider the problem of simplifying a triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made onto one of its adjacent vertices. In order to maintain a high number of contractible edges under this restriction, a small modification of the mesh around the edge to be contracted is allowed. Such a contraction is denoted a 2-step contraction. Given m "important" points or edges it is shown that a simplification hierarchy of size O(n) and depth O(log(n/m)) may be constructed in O(n) time. Further, for many edges not even 2-step contractions may be enough, and thus, the concept is generalized to k-step contractions.
|
|
| 2. |
- Grantson Borgelt, Magdalene, et al.
(författare)
-
Fixed parameter algorithms for the minimum weight triangulation problem
- 2008
-
Ingår i: International Journal of Computational Geometry and Applications. - 0218-1959. ; 18:3, s. 185-220
-
Tidskriftsartikel (refereegranskat)abstract
- We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n - 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.
|
|
| 3. |
- Andersson, Mattias, et al.
(författare)
-
Restricted mesh simplification using edge contractions
- 2009
-
Ingår i: International Journal of Computational Geometry and Applications. - 0218-1959. ; 19:3, s. 247-265
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of simplifying a planar triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made on to one of its adjacent vertices, which results in removing the other adjacent vertex. We show that if the perimeter of the mesh consists of at most five vertices, then we can always find a vertex not on the perimeter which can be removed in this way. If the perimeter consists of more than five vertices such a vertex may not exist. In order to maintain a higher number of removable vertices under the above restriction, we study edge flips which can be performed in a visually smooth way. A removal of a vertex which is preceded by one such smooth operation is called a 2-step removal. Moreover, we introduce the possibility that the user defines "important" vertices (or edges) which have to remain intact. Given m such important vertices, or edges, we show that a simplification hierarchy of size O(n) and depth O(log(n/m))can be constructed by 2-step removals in O(n) time, such that the simplified graph contains the m important vertices and edges, and at most O(m) other vertices from the input graph. In some triangulations, many vertices may not even be 2-step removable. In order to provide the option to remove such vertices, we also define and examine k-step removals. This increases the lower bound on the number of removable vertices.
|
|
