Combinatorial properties of one-dimensional arrangements

Frédéric Cazals 1, *
* Auteur correspondant
1 iMAGIS - Models, Algorithms and Geometry for Computer Generated Image Graphics
GRAVIR - IMAG - Graphisme, Vision et Robotique, Inria Grenoble - Rhône-Alpes
Abstract : Arrangements are an omni-present topic in computational geometry, since many problems in computer graphics and robotics reduce to the study of such sets. Motivated by two problems from these areas —more precisely from ray-tracing and assembly planning, we study in this paper the combinatorial structure of arrangements of segments on a line and of cones on a circle. We show that the numbers of such arrangements are respectively 1.3.5 . . . (2n−1) and (2n)!/n!, that the probabilities for the ith vertex of a random arrangement to be a beginning point are 1−(i−1)/(2n−1) and 1/2, and that the average numbers of segments or cones the ith vertex is contained in are (1−i)(i−2n)/(2n−1) and (n − 1)/2. In addition to providing results for the analysis of the the ray tracing related and assembly sequencing problems, the constructions used to prove these results provide sampling schemes for generating random inputs usable to test and validate the correctness of programs manipulating arrangements. Along with the derivation of these identities, we also point out connections between arrangements, sub-diagonal random walks and the ballot problem, as well as other integer sequences.
Type de document :
Article dans une revue
Experimental Mathematics, Taylor & Francis, 1997, 6 (1)
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00509987
Contributeur : Team Evasion <>
Soumis le : mardi 17 août 2010 - 13:59:18
Dernière modification le : jeudi 11 janvier 2018 - 06:20:04
Document(s) archivé(s) le : jeudi 18 novembre 2010 - 02:52:08

Fichiers

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

Identifiants

  • HAL Id : inria-00509987, version 1

Collections

INRIA | UGA | IMAG

Citation

Frédéric Cazals. Combinatorial properties of one-dimensional arrangements. Experimental Mathematics, Taylor & Francis, 1997, 6 (1). 〈inria-00509987〉

Partager

Métriques

Consultations de la notice

126

Téléchargements de fichiers

150