We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
3-Colored Triangulation of 2D Maps.
- Authors
Bueno, Lucas Moutinho; Stolfi, Jorge
- Abstract
We describe an algorithm to triangulate a general map on an arbitrary surface in such way that the resulting triangulation is vertex-colorable with three colors. (Three-colorable triangulations can be efficiently represented and manipulated by the GEM data structure of Montagner and Stolfi.) The standard solution to this problem is the barycentric subdivision, which produces triangles when applied to a map with edges, such that of them are border edges (adjacent to only one face). Our algorithm yields a subdivision with at most triangles, where is the Euler Characteristic of the surface; or at most triangles if all faces of the map have the same degree . Experimental results show that the resulting triangulations have, on the average, significantly fewer triangles than these upper bounds.
- Subjects
TRIANGULATION; ALGORITHMS; BARYCENTRIC dynamical time; EULER characteristic; MAPS; TOPOLOGY
- Publication
International Journal of Computational Geometry & Applications, 2016, Vol 26, Issue 2, p111
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195916500060