9
$\begingroup$

Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior. Let T be a triangulation of the whole disk with vertices on the labelled points such that T contains no self-loops except the boundary of the disk, no multiple edges between two points in the interior of T, arcs of T can be curved.

1) Does T have an Hamiltonian circuit ?

2) If R is another triangulation of the same time, how many flips (as a function of $ n $ should one perform at most in order to get from R to T ?

Improve this question
$\endgroup$
2
  • 6
    $\begingroup$ I don't get it. The face inside and adjacent to the boundary can only be a triangle if its other two edges join the same pair of vertices. But you ruled out multiple edges.. $\endgroup$ Commented Oct 15, 2013 at 4:06
  • 1
    $\begingroup$ You're right. No multiple edges between two points in the interior of the disk. I'll edit. $\endgroup$ Commented Oct 15, 2013 at 12:38

1 Answer 1

Reset to default
2
$\begingroup$
  1. Not necessarily.
  2. See the famous paper of Sleator/Tarjan/Thurston (Journal of the AMS, vol 1, issue 1, I believe).
Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I know that paper, it's about triangulations of a polygon. Labelled points are inside the disk in my case. Methods used are pure hyperbolic geometry (!) $\endgroup$ Commented Oct 15, 2013 at 2:35

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.