Some Algorithms for Computing Monotone Paths With Engineering Applications

In this thesis, we explore three problems related to monotonicity. Polygon partitioning is an important problem in computational geometry with a long history. In my master's thesis, I studied the problem of partitioning a polygon with holes into a minimum number of uniformly monotone components allowing arbitrary Steiner points. We call this the MUMC problem. In this thesis we provide an improved algorithm. We show that given a polygon with n vertices and h holes and a scan direction, the MUMC problem can be solved in time O(n log n + h log3 h ). Our algorithm produces a compressed representation of the subdivision of size O(n), from which it is possible to extract either the entire decomposition or just the boundary of any desired component, in time proportional to the output size. When the scan direction is not given, the problem can be solved in time O(K(n log n + h log3 h)), where K is the number of edges in the polygon's visibility graph. Our approach is quite different from existing algorithms for monotone decomposition. We show that in O( n log n) time the problem can be reduced to the problem of computing a maximum flow in a planar network of size O( h) with multiple sources and multiple sinks. The problem is then solved by applying any standard graph flow algorithm to the resulting network.;In the second work, we propose an algorithm for computing a shortest descending path from a start point s to a destination point t on a convex terrain. Our algorithm requires O(n log n) time and space, which is a logarithmic factor improvement of the existing fastest algorithm.;In the third work, we address the problem of answering monotone descent path queries on terrains that are continually changing. A terrain can be represented by a unique contour tree. Such a contour tree belongs to a class of graphs called arbitrarily directed trees (ADTs). In this thesis, we present a new linear time preprocessing algorithm for decomposing a static ADT T into a forest F, with which we can answer lowest common descendent (LCA) queries in O(1) time. This is useful in answering monotone path queries on the corresponding terrain. Next we show how to maintain this data structure for dynamic ADTs, and therefore answer LCA queries efficiently. We also show how to maintain the data structure of dynamic terrains in a relatively general setting, while simultaneously maintaining the corresponding contour tree. This allows us to efficiently answer monotone path queries between any two points on dynamic terrains.