Name
Abstract | ||
|---|---|---|
Let n ≥ 4 be even. It is shown that every set S of n points in the plane can be connected by a (possibly self-intersecting) spanning tour (Hamiltonian cycle) consisting of n straight line edges such that the angle between any two consecutive edges is at most 2π/3. For n = 4 and 6, this statement is tight. It is also shown that every even-element point set S can be partitioned into at most two subsets, S
1 and S
2, each admitting a spanning tour with no angle larger than π/2. Fekete and Woeginger conjectured that for sufficiently large even n, every n-element set admits such a spanning tour. We confirm this conjecture for point sets in convex position. A much stronger result
holds for large point sets randomly and uniformly selected from an open region bounded by finitely many rectifiable curves: for any ε> 0, these sets almost surely admit a spanning tour with no angle larger than ε.
|
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-11805-0_3 | Electronic Journal of Combinatorics |
Keywords | Field | DocType |
convex position,n-element set,n straight line,n point,large angle,even-element point,hamiltonian cycle,point set,open region,consecutive edge,large point,geometric graph,plane | Line (geometry),Discrete mathematics,Combinatorics,Spatial network,Hamiltonian (quantum mechanics),Hamiltonian path,Almost surely,Convex position,Conjecture,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
19 | 2 | 1077-8926 |
ISBN | Citations | PageRank |
3-642-11804-6 | 3 | 0.43 |
References | Authors | |
8 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adrian Dumitrescu | 1 | 458 | 66.11 |
| János Pach | 2 | 2366 | 292.28 |
| Géza Tóth | 3 | 581 | 55.60 |