In their seminal work on Multidimensional Sorting, Goodman and Pollack introduced the so-called order type, which for each ordered triple of a point set in the plane gives its orientation, clockwise or counterclockwise. This information is sufficient to solve many problems from discrete geometry where properties of point sets do not depend on the exact coordinates of the points but only on their relative positions. Goodman and Pollack showed that an efficient way to store an order type in a matrix λ of quadratic size (w.r.t. the number of points) is to count for every oriented line spanned by two points of the set how many of the remaining points lie to the left of this line. We generalize the concept of order types to bicolored point sets (every point has one of two colors). The bicolored order type contains the orientation of each bicolored triple of points, while no information is stored for monochromatic triples. Similar to the uncolored case, we store the number of blue points that are to the left of an oriented line spanned by two red points or by one red and one blue point in λ_B. Analogously the number of red points is stored in λ_R. As a main result, we show that the equivalence of the information contained in the orientation of all bicolored point triples and the two matrices λ_B and λ_R also holds in the colored case. This is remarkable, as in general the bicolored order type does not even contain sufficient information to determine all extreme points (points on the boundary of the convex hull of the point set).We then show that the information of a bicolored order type is sufficient to determine whether the two color classes can be linearly separated and how one color class can be sorted around a point of the other color class. Moreover, knowing the bicolored order type of a point set suffices to find bicolored plane perfect matchings or to compute the number of crossings of the complete bipartite graph drawn on a bicolored point set in quadratic time.

We study extremal problems about faces in convex rectilinear drawings of K_n, that is, drawings where vertices are represented by points in the plane in convex position and edges by line segments between the points representing the end-vertices. We show that if a convex rectilinear drawing of K_n does not contain a common interior point of at least three edges, then there is always a face forming a convex 5-gon while there are such drawings without any face forming a convex k-gon with k ≥ 6.

A convex rectilinear drawing of K_n is regular if its vertices correspond to vertices of a regular convex n-gon. We characterize positive integers n for which regular drawings of K_n contain a face forming a convex 5-gon.

To our knowledge, this type of problems has not been considered in the literature before and so we also pose several new natural open problems.

Let P be a set of n = 2m + 1 points in the plane in general position. We define the graph GM_P whose vertex set is the set of all plane matchings on P with exactly m edges. Two vertices in GM_P are connected if the two corresponding matchings have m − 1 edges in common. In this work we show that GM_P is connected.

Let P be a set of n = 2m + 1 points in the plane in general position. We define the graph GM_P whose vertex set is the set of all plane matchings on P with exactly m edges. Two vertices in GM_P are connected if the two corresponding matchings have m − 1 edges in common. In this work we show that GM_P is connected.

We study the problem of determining the complexity of the lower envelope of a collection of n geometric objects. For collections of rays; unit length line segments; and collections of unit squares to which we apply at most two transformations from translation, rotation, and scaling, we prove a complexity of Θ(n). If all three transformations are applied to unit squares, then we show the complexity becomes Θ(nα(n)), where α(n) is the slowly growing inverse of Ackermann’s function.

A k-transmitter g in a polygon P, with n vertices, k-sees a point p ∈ P if the line segment gp intersects P’s boundary at most k times. In the k-Transmitter Watchman Route Problem we aim to minimize the length of a k-transmitter watchman route along which every point in the polygon—or a discrete set of points in the interior of the polygon—is k-seen. We show that the k-Transmitter Watchman Route Problem for a discrete set of points is NP-hard for histograms, uni-monotone polygons, and star-shaped polygons given a fixed starting point. For histograms and uni-monotone polygons it is also NP-hard without a fixed starting point. Moreover, none of these versions can be approximated to within a factor c · log n, for any constant c > 0.

In this thesis, we investigate visibility in connection with path planning.  We focus on two problems concerning the exploration of and the orientation in an environment. 

The first problem we consider is the Watchperson Route Problem, in which mobile agents are deployed to monitor the interior of a 2-dimensional environment bounded by a polygon. The goal is to see (a) every part of, or (b) some points of interest in the environment at some point in time. To save resources, the route along which a mobile agent walks shall be as short as possible. We explore different variations of this problem, involving human vision as we know it, as well as a notion of vision that resembles that of a modem with the ability of seeing through some walls. Our research is driven by the question of finding an optimal solution―a shortest path―with efficient use of resources. As it turns out, some variations of the Watchperson Route Problem allow for computing optimal solutions with only short computation time, while other variations are provably difficult to solve optimally. For those variations that are hard to solve, we provide efficient algorithms to approximate optimal solutions.  

In the second problem, we are given an odd number of points in the plane, and non-intersecting segments such that each segment connects two of the points, leaving only one point unmatched. We ask whether it is possible to reconfigure this arrangement into any other arrangement of equally many non-intersecting segments on the given point set by gradually adding and removing one segment in such a way that after each reconfiguration step, the number of segments remains constant and only one point is unmatched. To keep this transformation planar, the segments are viewed as obstacles in the plane, and the visibility between the unmatched point and the segment endpoints is used to determine possible transformations. We prove that there always exists a sequence of reconfiguration steps that allows us to transform any given set of segments into any other set of segments on the same set of endpoints. 

We present an O(n² · min{m, n}) time and O(n · min{m, n}) storage algorithm to compute the minsum set of m watchmen routes given their starting points in a Stiegl polygon ― a staircase polygon where the floor solely consists of one horizontal and one vertical edge ― with n vertices.

In their seminal work on Multidimensional Sorting, Goodman and Pollack introduced the so-called order type, which for each ordered triple of a point set in the plane gives its orientation, clockwise or counterclockwise. This information is sufficient to solve many problems from discrete geometry where properties of point sets do not depend on the exact coordinates of the points but only on their relative positions. Goodman and Pollack showed that an efficient way to store an order type in a matrix λ of quadratic size (w.r.t. the number of points) is to count for every oriented line spanned by two points of the set how many of the remaining points lie to the left of this line.

We generalize the concept of order types to bicolored point sets (every point has one of two colors). The bicolored order type contains the orientation of each bicolored triple of points, while no information is stored for monochromatic triples. Similar to the uncolored case, we store the number of blue points that are to the left of an oriented line spanned by two red points or by one red and one blue point in λ_B. Analogously the number of red points is stored in λ_R.

We show that the equivalence of the information contained in the orientation of all bicolored point triples and the two matrices λ_B and λ_R also holds in the colored case. This is remarkable, as in general the bicolored order type does not even contain sufficient information to determine all extreme points (points on the boundary of the convex hull of the point set).

We study the problem of multiple watchman routes, where we are given m starting points for watchmen, and aim to find routes for all watchmen such that all points in a polygon are visible from at least one route. Domination among starting points is allowed. We consider the problem in Minbar polygons, which are staircase polygons for which the floor solely consists of one horizontal and one vertical edge, and in generalized Minbar polygons, which relax the definition of Minbar polygons, allowing for non-rectilinear edges. For Minbar polygons, we propose exact algorithms based on a dynamic-programming approach for both the min-max and the min-sum criterion. The min-max algorithm takes O(m log m + n log n) time, using O(m+n) storage, and the min-sum algorithm takes O(n² log m + m log m) time, using O(m+n) storage. For generalized Minbar polygons, we prove NP-hardness for the min-sum and min-max criteria, and present approximation algorithms for both criteria: an O(log(m+n))-approximation taking O(m⁴n²) time for the min-sum criterion, and a (π+3)-approximation taking O(m³n²) time for the min-max criterion. As corollaries of the NP-hardness, we show that both the min-sum and the min-max m-watchman route problem are NP-hard for watchmen moving on or above a terrain.