Back to Search
Start Over
BOUNDARY-OPTIMAL TRIANGULATION FLOODING.
- Source :
-
International Journal of Computational Geometry & Applications . Jun2006, Vol. 16 Issue 2/3, p271-290. 20p. 7 Diagrams. - Publication Year :
- 2006
-
Abstract
- Given a planar triangulation all of whose faces are initially white, we study the problem of colouring the faces black one by one so that the boundary between black and white faces as well as the number of connected black and white regions are small at all times. We call such a colouring sequence of the triangles a flooding. We prove that a flooding with boundary size ${\mathcal O}({\sqrt n})$ and ${\mathcal O}({\rm log}\,n)$ regions can be computed in ${\mathcal O}(n\,{\rm log}\,n)$ time. We also prove that it is in general impossible to guarantee boundary size ${\mathcal O} (n^{1-\epsilon})$, for any ∊ > 0, and a number of regions that is o(log n), where n is the number of faces of the triangulation. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 16
- Issue :
- 2/3
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 20594297
- Full Text :
- https://doi.org/10.1142/S0218195906002038