Full Record

Author | Nayyeri, Amir |

Title | Combinatorial optimization on embedded curves |

URL | http://hdl.handle.net/2142/42333 |

Publication Date | 2013 |

Date Accessioned | 2013-02-03 19:35:37 |

Degree | PhD |

Discipline/Department | 0112 |

Degree Level | doctoral |

University/Publisher | University of Illinois – Urbana-Champaign |

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 Z2-homology class. Given a directed graph embedded on a surface of genus g with b boundary cycles, we can compute the shortest single cycle Z2-homologous 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 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 is a 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 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 Z2-homology class is in general NP-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 genus g, 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 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 polynomial-time 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.… |

Subjects/Keywords | Computational topology; combinatorial optimization; curves; maximum flow; minimum cut; curve similarity; normal coordinated |

Contributors | Erickson, Jeff G. (advisor); Erickson, Jeff G. (Committee Chair); Har-Peled, Sariel (committee member); Forsyth, David A. (committee member); Dey, Tamal (committee member) |

Language | en |

Rights | Copyright 2012 Amir Nayyeri |

Country of Publication | us |

Record ID | handle:2142/42333 |

Repository | uiuc |

Date Indexed | 2020-03-09 |

Grantor | University of Illinois at Urbana-Champaign |

Issued Date | 2013-02-03 19:35:37 |

Sample Search Hits | Sample Images

…2.9 Piecewise linear surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.10 Curve *similarity* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.10.1 Frecht distance…

…Flows in sparse graphs . . . . . . . . . . . . . . . . . . . . . . . .
3.1.4 Flows and cuts in planar graphs . . . . . . . . . . . . . . . . . . .
3.1.5 Generalizations of planar cuts . . . . . . . . . . . . . . . . . . . .
3.2 Undirected minimum *cut* and…

…50]. See [58, 68, 92, 191] for more extensive surveys of applications.
We can think of any equivalence relation as a crude *similarity* measure, in which
two curves are at distance 0 if they are equivalent and distance ∞ if they are not…

…More refined *similarity* measures can be defined by considering the geometry of
the underlying space. Measures of *similarity* like Hausdorff distance, earth mover
distance and the Frecht distance have found several applications in computer
science […

…120, 123, 148, 178]. For embedded curves on a surface, and particulary
for homotopic curves, a natural measure of *similarity* is the minimum “cost” of a
deformation of one curve to the other. Different costs of deformation has been
considered in…

…minimum
3
*cut* [39], computing the minimum non-separating cycle, computing the minimum
non-contractible cycle [76, 183], computing a tight system of loops and computing
a short *cut* graph [79]. See Chapter 3 for more…

…method.
1.2
New results
In this thesis we consider several computational problems about embedded curves
on surfaces. We mostly focus on problems that are related to classification of curves
and measuring their *similarity*. In Chapter 2 we briefly…

…114] recently improved the running time of our algorithm
to g O(g) n log log n.
Given a graph embedded on a surface and two vertices s and t, we prove that
the minimum (s, t)-*cut* is dual to shortest even subgraph in a certain…