In this thesis, we explore two problems in geometry, both related to monotonicity. The problem of finding monotone paths between two given points has useful applications in path planning, and in particular it is useful to look for minimum link paths. We are given a simple polygon P or a polygonal domain D with n vertices, and a triplet of query parameters: (s, t, d), where s and t are two points in the plane and d is any direction. We show how to answer a query for the existence of a d-monotone path between s and t inside P (or D) in logarithmic time by preprocessing P (or D) in an efficient way. Our approach is based on a novel idea utilizing the dual graph of the trapezoidal map of P (or D). Furthermore, we also show how to output a minimum link d-monotone path between points s and t,...[ Read more ]

In this thesis, we explore two problems in geometry, both related to monotonicity. The problem of finding monotone paths between two given points has useful applications in path planning, and in particular it is useful to look for minimum link paths. We are given a simple polygon P or a polygonal domain D with n vertices, and a triplet of query parameters: (s, t, d), where s and t are two points in the plane and d is any direction. We show how to answer a query for the existence of a d-monotone path between s and t inside P (or D) in logarithmic time by preprocessing P (or D) in an efficient way. Our approach is based on a novel idea utilizing the dual graph of the trapezoidal map of P (or D). Furthermore, we also show how to output a minimum link d-monotone path between points s and t, for an arbitrary input triplet (s, t, d).

Polygon partitioning is another important problem in computational geometry. We address the problem of partitioning a polygonal domain D into a minimum number of uniformly monotone components, allowing Steiner points. We show that for a given monotone direction, this problem is solvable in O(nlogn + rR) time, where n is the number of vertices of D, r is the number of scan reflex vertices of D, and R is the total number of reflex vertices of D. Further, if E is the size of the visibility graph of the polygon, then the optimal uniformly monotone subdivision can be queried in O(E(n + R^1.5log²R)) time, and reported in O(rR) time. We also provide upper bounds on the number of components as well as on the number of Steiner points in such an optimal subdivision.