The Library
Polynomial-time efficient position
Tools
Kuhne, Ronja Johanna Barbara (2019) Polynomial-time efficient position. PhD thesis, University of Warwick.
|
PDF
WRAP_Theses_Kuhne_2019.pdf - Submitted Version - Requires a PDF viewer. Download (997Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b3493313~S15
Abstract
Suppose that S is a surface of positive complexity and N ⊂ S a tie neighbourhood of a large train track τ in S. We present a polynomial-time algorithm that, given a properly immersed, essential, and non-peripheral arc or curve α ⊂ S, homotopes α into efficient position with respect to the tie neighbourhood N.
Proofs for the existence of efficient position were previously given in [Tak00] and [MMS12]. In [Tak00], a constructive proof for the existence of efficient position is given for immersed curves on closed surfaces of genus greater than or equal to two. There is no discussion of the complexity of the implied algorithm. In [MMS12], the existence of efficient position is proved for embedded curves with respect to birecurrent train tracks on surfaces of positive complexity. The implied algorithm operates via an exhaustive search. No time bounds can be deduced.
We note that the algorithm presented in this thesis and the algorithm suggested by a careful reading of [Tak00] coincide in the case of closed surfaces. However, this thesis constitutes more than a time-complexity analysis of Takarajima’s constructive proof. Firstly, we are more general as we allow surfaces with boundary, whereas Takarajima only considers closed surfaces. Secondly, our combinatorial set-up uses arcs and curves with transverse self-intersection, whereas the barycentric subdivision of complementary regions carried out in [Tak00] forces non-transverse self-intersection even for curves which are initially embedded. Thirdly, the algorithm in this thesis is formulated purely in terms of local homotopies, whereas [Tak00] requires semi-local arguments. Thus, we can, and do, give pseudocode for our algorithm as well as prove its correctness.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Polynomials | ||||
Official Date: | August 2019 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Mathematics Institute | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Schleimer, Saul ; Bowditch, B. H. (Brian Hayward), 1961- | ||||
Sponsors: | Engineering and Physical Sciences Research Council | ||||
Format of File: | |||||
Extent: | xiv, 114 leaves : illustrations (some colour) | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year