mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Defenses » November 2017 » Alexandros Angelopoulos Anonymously browsing from 54.162.139.105 at 18:21:37, 24-11-2017. login
download defense details: { pdf }

MSc thesis defense presentation

Alexandros Angelopoulos defends his MSc thesis

Date: Friday, 10 Nov 2017
Time: 18:00
Location: School of Electrical and Computer Engineering (old buildings), 1.1.31
Thesis title: Triangulation Problems on Geometric Graphs - Sampling over Convex Triangulations
Committee:

Thesis abstract

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.

Reporter

Page updates

No recent updates.

Feeds RSS and Atom feeds

posts
all posts RSS
news RSS
announcements RSS
website news RSS
events
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.