[Back]

M. Birsak:
"Discrete Optimization on Graphs and Grids for the Creation of Navigational and Artistic Imagery";
Supervisor, Reviewer: M. Wimmer, R. Sablatnig, P. Wonka; 193-02, 2018; oral examination: 2018-10-17.

Optimization has become an important tool for many research communities and is used
to find a good feasible solution for a variety of problems. One important subarea that
attracts special interest is discrete optimization, which is characterized by integer variables
in the problem formulation. The particular attention discrete optimization gets is caused
by the close relation to some well-known combinatorial problems encountered in real life
as well as hard problems for which methods that can solve them in polynomial time are
unknown. Due to their inherent discrete structure, two domains that almost naturally
reveal a multitude of discrete optimization problems are graphs and grids.
In this thesis, three peer-reviewed publications are presented that can be categorized into
two different topics - navigation and arts - that have one fundamental aspect in common:
they are all based on discrete optimization and use graphs and grids as their central
computational domains. First, we present a method for the Automatic Generation of
Tourist Brochures. These brochures are static printable maps that provide both essential
information about some points of interest (POIs) as well as navigational instructions to
tell the user how to travel between any pair of POIs. We incorporate several approved
design guidelines into our optimization approach to obtain maps that are easily readable
and can be printed on paper without visual clutter.
Second, we try to improve on the findings from our first publication to accomplish a
switch from a static to a dynamic output. We propose a framework for Dynamic Path
Exploration on Mobile Devices that allows the user to create custom visualizations that
allow an easy exploration of an unfamiliar region. Again, we utilize discrete optimization
to compute an interesting path through the environment as well as to find positions for
rectangular entities that encapsulate important information about the POIs in proximity
to the path.
Finally, we utilize our insights about discrete optimization to obtain an artistic output.
In our proposed system, we aim at a fully automatic fabrication pipeline to create String
Art. We present a greedy solver for binary non-linear least squares problems together
with an adaption of an algorithm used for Euler-Path-Computation to obtain a sequence
of strings that allows the fabrication using one continuous piece of textile thread. For the
actual fabrication, we propose a hardware setup using a high-precision industrial robot, a
tension regulator from a professional knitting machine and a custom-made winding tool.

https://publik.tuwien.ac.at/files/publik_273373.pdf