We describe several algorithms for classifying, comparing and optimizing curveson surfaces. We give algorithms to compute the minimum member of a givenhomology class, particularly computing the maximum flow and minimum cuts,in surface embedded graphs. We describe approximation algorithms to computecertain similarity measures for embedded curves on a surface. Finally, we presentalgorithms to solve computational problems for compactly presented curves.We describe the first algorithms to compute the shortest representative of aZ2-homology class. Given a directed graph embedded on a surface of genus gwith b boundary cycles, we can compute the shortest single cycle Z2-homologousto a given even subgraph in 2^{O(g+b)}nlog n time. As a consequence we obtain analgorithm to compute the shortest directed non-separating cycle in 2^{O(g)}n log n time,which improves the previous best algorithm by a factor of O(\sqrt{n}) if the genus isa constant. Further, we can compute the shortest even subgraph in a given Z2-homology class if the input graph is undirected in the same asymptotic runningtime. As a consequence, we obtain the first near linear time algorithm to computeminimum (s, t)-cuts in surface embedded graphs of constant genus. We also provethat computing the shortest even subgraph in a Z2-homology class is in generalNP-hard, which explains the exponential dependence on g.We also consider the corresponding optimization problem under Z-homology.Given an integer circulation \Phi in a directed graph embedded on a surface of genusg, we describe algorithms to compute the minimum cost circulation that is Z-homologous to \Phi in O(g^8n log^2 n log^2 C) time if the capacities are integers whosesum is C or in g^{O(g)}n^{3/2} time for arbitrary capacities. In particular, our algorithmimproves the best known algorithm for computing the maximum (s, t)-flow onsurface embedded graph after 20 years. The previous best algorithm, except forplanar graphs, follow from general maximum flow algorithms for sparse graphs.Next, we consider two closely related similarity measures of curves on piecewiselinear surfaces embedded in R^3, called homotopy height and homotopic Frechét distance.These similarity measures capture the longest curve that appears and thelongest length that any point travels in the best morph between two given curves, respectively.We describe the first polynomial-time O(log n)-approximation algorithmsfor both problems. Prior to our work no algorithms were known for the homotopyheight problem. For the homotopic Frechét distance, algorithms were known onlyfor curves on Euclidean plane with polygonal obstacles. Surprisingly, it is not evenknown if deciding if either the homotopy height or the homotopic Frechét distanceis smaller that a given value is in NP.Finally, we consider normal curves on abstract triangulated surfaces. A curveis normal if it intersects any triangle in a finite set of arcs, each crossing betweentwo different edges of the triangle. Given a triangulated surface of complexityn and a curve that crosses the triangulation X times, we can build another celldecomposition of the input surface of complexity O(n), in O(min(X, n^2 log X)) time,whose 1-skeleton contains the input curve. We emphasize the the cell decompositionalgorithm takes polynomial time even if X is exponential. The main ingredient of ourcell decomposing algorithm is a technique to trace a curve in a triangulated surface.We apply our abstract tracing strategy to solve well-known problems about normalcurves including computing the number of components, computing the numberof isotopy classes and computing the algebraic intersection number between twocurves. Our normal-coordinate algorithms are competitive with and conceptuallysimpler than earlier algorithms.
PDF
download
878987797
028-85220240
