
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 + R1.5log2R)) 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.
Polygons, Monotone operators, 511, Geometry -- Data processing
Polygons, Monotone operators, 511, Geometry -- Data processing
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
