Files in this item
Files  Description  Format 

application/pdf Amir_Nayyeri.pdf (2MB)  (no description provided) 
Description
Title:  Combinatorial optimization on embedded curves 
Author(s):  Nayyeri, Amir 
Director of Research:  Erickson, Jeff G. 
Doctoral Committee Chair(s):  Erickson, Jeff G. 
Doctoral Committee Member(s):  HarPeled, Sariel; Forsyth, David A.; Dey, Tamal 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Computational topology
combinatorial optimization curves maximum flow minimum cut curve similarity normal coordinated 
Abstract:  We describe several algorithms for classifying, comparing and optimizing curves on surfaces. We give algorithms to compute the minimum member of a given homology class, particularly computing the maximum flow and minimum cuts, in surface embedded graphs. We describe approximation algorithms to compute certain similarity measures for embedded curves on a surface. Finally, we present algorithms to solve computational problems for compactly presented curves. We describe the first algorithms to compute the shortest representative of a Z2homology class. Given a directed graph embedded on a surface of genus g with b boundary cycles, we can compute the shortest single cycle Z2homologous to a given even subgraph in 2^{O(g+b)}nlog n time. As a consequence we obtain an algorithm to compute the shortest directed nonseparating 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 is a constant. Further, we can compute the shortest even subgraph in a given Z2homology class if the input graph is undirected in the same asymptotic running time. As a consequence, we obtain the first near linear time algorithm to compute minimum (s, t)cuts in surface embedded graphs of constant genus. We also prove that computing the shortest even subgraph in a Z2homology class is in general NPhard, which explains the exponential dependence on g. We also consider the corresponding optimization problem under Zhomology. Given an integer circulation \Phi in a directed graph embedded on a surface of genus g, we describe algorithms to compute the minimum cost circulation that is Zhomologous to \Phi in O(g^8n log^2 n log^2 C) time if the capacities are integers whose sum is C or in g^{O(g)}n^{3/2} time for arbitrary capacities. In particular, our algorithm improves the best known algorithm for computing the maximum (s, t)flow on surface embedded graph after 20 years. The previous best algorithm, except for planar graphs, follow from general maximum flow algorithms for sparse graphs. Next, we consider two closely related similarity measures of curves on piecewise linear surfaces embedded in R^3, called homotopy height and homotopic Frechét distance. These similarity measures capture the longest curve that appears and the longest length that any point travels in the best morph between two given curves, respectively. We describe the first polynomialtime O(log n)approximation algorithms for both problems. Prior to our work no algorithms were known for the homotopy height problem. For the homotopic Frechét distance, algorithms were known only for curves on Euclidean plane with polygonal obstacles. Surprisingly, it is not even known if deciding if either the homotopy height or the homotopic Frechét distance is smaller that a given value is in NP. Finally, we consider normal curves on abstract triangulated surfaces. A curve is normal if it intersects any triangle in a finite set of arcs, each crossing between two different edges of the triangle. Given a triangulated surface of complexity n and a curve that crosses the triangulation X times, we can build another cell decomposition of the input surface of complexity O(n), in O(min(X, n^2 log X)) time, whose 1skeleton contains the input curve. We emphasize the the cell decomposition algorithm takes polynomial time even if X is exponential. The main ingredient of our cell decomposing algorithm is a technique to trace a curve in a triangulated surface. We apply our abstract tracing strategy to solve wellknown problems about normal curves including computing the number of components, computing the number of isotopy classes and computing the algebraic intersection number between two curves. Our normalcoordinate algorithms are competitive with and conceptually simpler than earlier algorithms. 
Issue Date:  20130203 
URI:  http://hdl.handle.net/2142/42333 
Rights Information:  Copyright 2012 Amir Nayyeri 
Date Available in IDEALS:  20130203 
Date Deposited:  201212 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois