1
$\begingroup$

Hi

I am given a triangulation $T $ of a set of points $S $ in the plane and a disk $D$ which doesn't contain any triangle. If I now look at the subgraph $G(V,E)$ of $T $ whose vertices are the points of $S$ contained in $D$ and whose edges are the edges of $T $ which are fully contained in $D $ then what can I say about $G$, if $|V|$ is sufficiently large, lets say bigger than 4?

Obviously $G$ is acyclic. Furthermore, a bit informal, each vertex $v$ needs to see some portion of the boundary of $D$ on both sides of any path through $v$.

But are there any other characteristics which have to hold for $G$?

Thank you

andy

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ This is a comment instead of an answer since I omit so many details. It's fairly easy to see that $G$ can be any tree. Fix a root and lay out the tree in such a way that the angle between any two children of a vertex is very small. If you do this with increasingly small angles as you move away from the root, you can complete the triangulation using points on an arc very far away from the tree, so that the tree is at the centre of the circle containing the arc. I believe it should be straightforward to modify the construction so that $G$ can actually be any acyclic graph. $\endgroup$
    – Andrew D. King
    Commented Dec 9, 2011 at 13:47

1 Answer 1

Reset to default
1
$\begingroup$

$G$ isn't necessarily connected.

Take a pentagon, $1,2,3,4,5$ with $D$ containing $3$ of it's vertices (say $1,3,4$). Triangulate the pentagon with $(2,4)$ and $(2,5)$. You can put it inside a bounding triangle with all the proper edges to get it to be a valid triangulation.

Then, $G$ contains no triangle, and consists of vertices $1,3,$ and $4$, along with edge $(3,4)$, and isn't connected.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .