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.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 1991, 1 (2), pp.187-196. 〈10.1142/S021819599100013X〉
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00167176
Contributeur : Olivier Devillers <>
Soumis le : jeudi 16 août 2007 - 11:55:14
Dernière modification le : mercredi 7 mars 2018 - 10:26:36
Document(s) archivé(s) le : vendredi 9 avril 2010 - 00:47:40

Fichier

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

197

Téléchargements de fichiers

95