Feedback

Faculté des Sciences appliquées
Faculté des Sciences appliquées
MASTER THESIS
VIEW 89 | DOWNLOAD 96

Master thesis : Symbolic representation of polygons in discrete spaces

Download
Bertrand, Alexis ULiège
Promotor(s) : Boigelot, Bernard ULiège
Date of defense : 26-Jun-2023/27-Jun-2023 • Permalink : http://hdl.handle.net/2268.2/17643
Details
Title : Master thesis : Symbolic representation of polygons in discrete spaces
Translated title : [fr] Représentation symbolique des polygones dans des espaces discrets
Author : Bertrand, Alexis ULiège
Date of defense  : 26-Jun-2023/27-Jun-2023
Advisor(s) : Boigelot, Bernard ULiège
Committee's member(s) : Fontaine, Pascal ULiège
Louveaux, Quentin ULiège
Language : English
Keywords : [en] Verification
[en] Computer Science
[en] Mesh
[en] Polyhedron
Discipline(s) : Engineering, computing & technology > Computer science
Target public : Researchers
Professionals of domain
Student
Institution(s) : Université de Liège, Liège, Belgique
Degree: Master en sciences informatiques, à finalité spécialisée en "computer systems security"
Faculty: Master thesis of the Faculté des Sciences appliquées

Abstract

[en] This master's thesis describes a new data structure called Discrete Polyhedron Decision Diagram (DPDD), suited for representing symbolically meshed polygons, i.e., the intersection between a discrete mesh and a convex polygon. We develop algorithms for manipulating the data structure such as performing the intersection of a meshed polygon with a set of constraints, or adding points to the structure. Each algorithm is thoroughly explained and presented in pseudo-code. Some examples are also given to illustrate important properties and operations. This master's thesis provides as well a prototype of the data structure in which all the main operations have been implemented.

The data structure is based on the double description method and automata-based representations. DPDD then explicitly stores the face lattice of the polygon while each of its faces also contain meshes. An advantage of this is that we can retrieve the canonical form of any meshed polygon thanks to a rounding process. This leads us to have more efficient operations over the data structure. We are able to easily and efficiently check whether two meshed polygons are equal, as example, and as we have the submesh of each face, we can avoid redundant computations.


File(s)

Document(s)

File
Access Symbolic_representation_of_polygons_in_discrete_spaces.pdf
Description:
Size: 1.06 MB
Format: Adobe PDF

Annexe(s)

Author

  • Bertrand, Alexis ULiège Université de Liège > Master sc. informatiques, à fin.

Promotor(s)

Committee's member(s)

  • Fontaine, Pascal ULiège Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes informatiques distribués
    ORBi View his publications on ORBi
  • Louveaux, Quentin ULiège Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation : Optimisation discrète
    ORBi View his publications on ORBi
  • Total number of views 89
  • Total number of downloads 96










All documents available on MatheO are protected by copyright and subject to the usual rules for fair use.
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.