National and Kapodistrian University of Athens
High-dimensional polytopes defined by oracles: algorithms, computations and applications
Abstract
dc:descriptionThe processing and analysis of high dimensional geometric data plays a fundamental role in disciplines of science and engineering. The last decades many successful geometric algorithms has been developed in 2 and 3 dimensions. However, in most cases their performance in higher dimensions is poor. This behavior is commonly called the curse of dimensionality. A solution framework adopted for the healing of the curse of dimensionality is the exploitation of the special structure of the data, such as sparsity or low intrinsic dimension and the design of approximation algorithms. The main research area of this thesis is discrete and computational geometry and its connections to branches of computer science and applied mathematics. The contribution of this thesis is threefold. First, the design and analysis of geometric algorithms for problems concerning high-dimensional, convex polytopes, such as convex hull and volume computation and their applications to computational algebraic geometry and optimization. Second, the establishment of combinatorial characterization results for essential polytope families. Third, the implementation and experimental analysis of the proposed algorithms and methods. The developed software is open-source, publicly available and builds on and extends state-of-the-art geometric and algebraic software libraries such as CGAL and polymake.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2014
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Fisikopoulos, Vissarion
- Φυσικόπουλος, Βησαρίων
Subjects
dc:subject × 20- Πολύτοπα
- Υπολογιστική γεωμετρία
- Υπολογισμός όγκου
- Υλοποιήσεις αλγορίθμων
- Τριγωνοποίησεις
- Πολύτοπο της αραιής απαλείφουσας
- Γεωμετρικά κατηγορήματα
- Πειραματική ανάλυση
- Convex polytopes
- Computational geometry
- Volume computation
- Triangulations
- Newton polytope of the sparse resultant
- Geometric predicates
- Experimental analysis
- Algorithm engineering
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/38844