On the central path and related problems

Recent technological developments, including GPS, mobile devices, and RFID tags, have made effective data collection and analysis a necessity. Such kind of data can usually be represented by paths. For example, paths represent the movement of the device carriers like vehicles, patients, animals, commodities, hurricane, etc. To extract the pattern of this type of data, we need to find the “center” of a given set of input paths. In this dissertation, we study the problem of finding the central path and some related problems. The first problem we study is the Farthest Color Voronoi Diagram (FCVD) and a special FCVD called Farthest-polygon Voronoi Diagram (FPVD). Given n line segments in the plane with each colored by one of k colors, the Farthest Colored Voronoi Diagram (FCVD) is a subdivision of the plane such that the region of a c-colored site (segment or subsegment) s contains all points of the plane for which c is the farthest color and s is the nearest c-colored site. FCVD is a generalization of the Farthest Voronoi Diagram (i.e., k = n) and the regular Voronoi Diagram (i.e., k = 1). In this dissertation, we first present a simple algorithm to solve the general FCVD problem in an output-sensitive fashion in O((kn + I)α(H)log n) time, where I is the number of intersections of the input and H is the complexity of the FCVD. We then focus on a special case, called Farthest-polygon Voronoi Diagram (FPVD), in which all colored segments form k disjoint polygonal structures (i.e., simple polygonal curves or polygons) with each consisting of segments with the same color. For FPVD, we present an improved algorithm with a running time of O(n log2 n). Our algorithm has better performance and is simpler than the best previously known O(n log3 n)-time algorithm. The second problem we study is the Central Path Problem (CPP) for finding the central path of a set of polygonal curves. A Central Path is a path that best represents a set of input paths. Various approaches have been proposed to define “best” in the literature depending on applications. In this problem we are given m polygonal curves Q = {P 1, P2, …,Pm} in 2D space and require that our central path P minimizes the maximum distance (measured by the directed Hausdorff distance) to paths in Q and is the locus of the centers of minimal spanning disks of Q. In such central path problems, the input curves in Q can be arbitrary, say, non-disjoint, not simple, and unrealistically intertwined. Thus the central path is rather complex in the worst case. We present a disk-sweeping algorithm to find a central path in O((n + s)k log m log2 n) time which is bounded by O(n22α( n) log n), where n is the size of Q, s the total number of self-intersecting points in Q, m is the total number of input curves, k is the size of the visited portion of FPVD of Q by the central path algorithm. The third problemwe study is the 2-Central Path Problem (2CPP) which is a generalization of the CPP. Basically, 2CPP aims to find two paths Pu and Pl such that there exists parametrizations fu( t) and fl(t) ( t ∈ [a, b]) of P u and Pl respectively such that the maximum distance from {fu(t), fl(t)} to curves in Q is minimized. We designed an algorithm that constructs Pu and Pl in O(nm log4 n2α( n)α(n)) time, where n is the total complexity of Q (i.e., the total number of vertices and edges), m is the number of curves in Q, and α(n) is the inverse Ackermann function. Our algorithm uses parametric search technique and is considerably faster than arrangement-related algorithms (i.e. Ω(n 2)) when m << n as in most real applications. The fourth problem we study is an interesting problem called Geometric Spanner Problem (GSP) which is seemingly unrelated to the central path but actually closely related to the construction of the input paths in Q from collected data. Geometric spanner is also a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this dissertation, we consider the following generalized geometric spanner problem under L 1 distance: Given a set of disjoint objects S, find a spanning network G with minimum size so that for any pair of points in different objects of S, there exists a path in G with length no more than t times their L1 distance, where t is the stretch factor. Specifically, we focus on three types of objects: rectilinear segments, axis aligned rectangles, and rectilinear monotone polygons. By combining ideas of t-weekly dominating set, walls, aligned pairs and interval cover, we develop a 4-approximation algorithm (measured by the number of Steiner points) for each type of objects. Our algorithms run in near quadratic time, and can be easily implemented for practical applications.