Computing the Union of 3-Colored Triangles - Archive ouverte HAL Access content directly
Journal Articles International Journal of Computational Geometry and Applications Year : 1991

## Computing the Union of 3-Colored Triangles

(1) , (1) , (2)
1
2
Jean-Daniel Boissonnat
• Function : Author
• PersonId : 830857
Olivier Devillers
Franco P. Preparata
• Function : Author

#### Abstract

Given is a set \s\ of $n$ points, each colored with one of $k \geq 3$ colours. We say that a triangle defined by three points of \s\ is 3-colored if its vertices have distinct colours. We prove in this paper that the problem of constructing the boundary of the union \ts\ of all such 3-colored triangles can be done in optimal $O(n \log n)$ time.

### Dates and versions

inria-00167176 , version 1 (16-08-2007)

### Identifiers

• HAL Id : inria-00167176 , version 1
• DOI :

### Cite

Jean-Daniel Boissonnat, Olivier Devillers, Franco P. Preparata. Computing the Union of 3-Colored Triangles. International Journal of Computational Geometry and Applications, 1991, 1 (2), pp.187-196. ⟨10.1142/S021819599100013X⟩. ⟨inria-00167176⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

67 View