inria-00167176, version 1
Computing the Union of 3-Colored Triangles
Jean-Daniel Boissonnat
1Olivier Devillers a, 1Franco Preparata b, 2
International Journal of Computational Geometry & Applications 1, 2 (1991) 187-196
Résumé : 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.
- a – INRIA
- b – John Brown University
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- 2 : Department of Computer Science (Brown University)
- Brown University
- Domaine : Informatique/Géométrie algorithmique
- inria-00167176, version 1
- http://hal.inria.fr/inria-00167176
- oai:hal.inria.fr:inria-00167176
- Contributeur : Olivier Devillers
- Soumis le : Jeudi 16 Août 2007, 11:55:14
- Dernière modification le : Jeudi 16 Août 2007, 11:59:42
Documents associés
Exporter