| Attributes | Values |
|---|
| type
| |
| Thesis advisor
| |
| Author
| |
| alternative label
| - Arrangements of rays, application to planar shapes reconstruction
|
| dc:subject
| - Robotique
- Thèses et écrits académiques
- Géométrie algorithmique
- Structure de données
- Analyse d'algorithmes
- Arrangement de rayons
- Reconstruction de formes
|
| preferred label
| - Arrangements de rayons, application à la reconstruction de formes planes
|
| Language
| |
| Subject
| |
| dc:title
| - Arrangements de rayons, application à la reconstruction de formes planes
|
| Degree granting institution
| |
| note
| - Cette thèse présente un travail de recherche en Algorithmique Géométrique et en Robotique concernant les arrangements de rayons dans le plan. Un rayon est une courbe semi-infinie qui représente par, exemple, un rayon lumineux servant à mesurer un point sur le bord d'un objet (l'extrémité du rayon).En premier lieu on montre qu'on peut définir un ordre total sur l'ensemble P des points mesurés (les extrémités des rayons) si et seulement si les points de P appartiennent à un objet unique et simplement connexe. Nous développons ensuite des algorithmes qui permettent de calculer en temps optimal soit l'ordre total sur l'ensemble P (dans le cas où les points de P appartiennent à un objet unique) soit les k sous-ordres partiels (dans le cas où les points de P appartiennent à k objets).La division des points de P en k sous-ensembles ordonnés permet de relier les points voisins de chaque sous-ensemble, par des arêtes, et de construire ainsi une approximation polygonale du bord de chaque objet. De plus, on peut construire en temps optimal, une quelconque des cellules de l'arrangement des rayons. Ceci permet notamment de calculer les k plus petites régions dont on est sûr qu'elles contiennent les k objets.Nous montrons également comment la notion d'ordre permet de reconstruire de façon exacte des formes polygonales, et ceci avec un nombre minimal de mesures. On généralise ainsi la technique connue sous le nom de probing dans la littérature anglo-saxonne.En plus des résultats sur les arrangements de rayons, nous présentons un résultat combinatoire sur le nombre maximal de tétraèdres des triangulations en dimension 3.
- This thesis presents a research in Computational Geometry and in Robotics, concerning the arrangements of rays in the plane. A ray is a semi-infinite curve which represents, for example, a light ray intended to measure a point on the boundary of an object (the ray terminus).First we show that we can define a total order on the set P of the measured points (the rays termini), if and only if these points belong to a unique and simply connected object. Then we develop algorithms which permit to calculate in optimal time, either the total order on the set P (in the case where the points of P belong to a unique object), or the k partial sub-orders (in the case where the points of P belong to k objects).The division of the points of P in k ordered sub-sets, allows to link the adjacent points of each sub-set by edges and thus to construct a polygonal approximation of the boundary of each object. Moreover, we can construct in optimal time anyone of the cells of the rays' arrangement. This allows, in particular, to compute the k smallest regions which, for sure, contain the k objects.We show also how the order relation can be used to determine the exact shape of a polygonal object by means of a minimum number of probes. We thus generalize the technique of probing.Besides the results on rays' arrangements, we present a combinatorial result on the maximum number of tetrahedra in 3-dimensional triangulations.
|
| dc:type
| |
| http://iflastandar...bd/elements/P1001
| |
| rdaw:P10219
| |
| has content type
| |
| is primary topic
of | |
| is rdam:P30135
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
