Computing the Union of 3-Colored Triangles

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/inria-00167176
Contributor : Olivier Devillers <>
Submitted on : Thursday, August 16, 2007 - 11:55:14 AM
Last modification on : Wednesday, March 7, 2018 - 10:26:36 AM
Long-term archiving on : Friday, April 9, 2010 - 12:47:40 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

214

Files downloads

160