Discrete optimization on graphs and grids for the creation of navigational and artistic imagery

Abstract

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.