Postgraduate Thesis uoadl:2286251 362 Read counter

Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού

Library of the School of Science

Library of the School of Science

2017-11-23

2017

Angelopoulos Alexandros

Αριστείδης Παγουρτζής, Αναπληρωτής Καθηγητής Ε.Μ.Π.

Ευστάθιος Ζάχος, Ομότιμος Καθηγητής Ε.Μ.Π.

Δημήτρης Φωτάκης, Επίκουρος Καθηγητής Ε.Μ.Π.

Ευστάθιος Ζάχος, Ομότιμος Καθηγητής Ε.Μ.Π.

Δημήτρης Φωτάκης, Επίκουρος Καθηγητής Ε.Μ.Π.

TRIANGULATION PROBLEMS ON GEOMETRIC GRAPHS - SAMPLING OVER CONVEX TRIANGULATIONS

English

TRIANGULATION PROBLEMS ON GEOMETRIC GRAPHS - SAMPLING OVER CONVEX TRIANGULATIONS

A geometric graph is a set of points V on the plane and a set of straight line segments E with endpoints in V, potentially and instinctively associated with the abstract G(V,E). When studying its thickness, i.e. partitioning its edges into crossing-free subsets (an NP-hard optimization problem), the problem of triangulation existence as a crossing-free subset T of the edges naturally occurs, as a triangulation of V is the largest such possible set that may be defined on V. In this Thesis, we examine a family of triangulation existence problems and classify them with respect to their complexity, both for their decision and their counting versions. The general case decision problem is the only one appearing in bibliography (Lloyd, 1977, NP-hard), while we deal with the convex case restriction and an "intermediate" polygon triangulation existence problem, fixing a new 2 by 2 table of results. In the final chapter, we modify our framework in order to build an exact uniform sampling and optimal coding algorithm for convex triangulations, which outperforms any known algorithm to date.

Science

Mathematics

geometric graph, triangulation existence, complexity, counting complexity, convex triangulations sampling

Yes

1

Yes

42

55