0
$\begingroup$

I'm working on a triangle partitioning problem, and I'm trying to find and prove some properties of specific triangulations. The triangulations I'm dealing with are constrained delaunay triangulations in which every constraint is at least an edge (there are no single vertex constraints). Here is an example of such a triangulation:

enter image description here

The red lines represent edge constraints and the blue lines represent the unconstrained edges produced to create the triangulation. Notice how all vertices are in some edge constraint and that there will never be a vertex that is not connected to a constrained edge.

Now let us create a graph from this triangulation. Every triangle is a vertex, and edges are defined by $(v_1,v_2)$ where $v_1$ and $v_2$ are triangles that share an unconstrained edge. Notice that every vertex in this graph has degree at most 3.

My problem is that I want to say something about the number of 3 degree vertices in such a graph. I believe that at least half the vertices have less than degree 3 (just from a hunch) but I have no idea how to go about proving such a thing. What I'm asking is, what is the upper bound of the ratio degree 3 vertices to total vertices in a triangulation with these properties.

EDIT: I found this on the delaunay triangulation wikipedia page. Delaunay triangulations have $O(n^{d/2})$ simplicies, so a planar DT would have $O(n)$ triangles where $n$ is the number of vertices. This isn't the same as the set of constrained delaunay triangulations we're working with, but it seems to suggest that there could be a relationship degree-3 triangles and the total number of triangles.

http://www.sciencedirect.com/science/article/pii/092577219500013Y

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you sure we can always obtain a delaunay triangulation? May be input configuration is in such a way that doesn't allow any possible delaunay triangulation. (I don't know if such an input exists or not but if you have a criteria such that every input configuration admits delaunay triangulation, then is better to mention it in the question). $\endgroup$
    – Saeed
    Jul 22, 2014 at 21:38
  • $\begingroup$ We don't need a delaunay triangulation, just a constrained delaunay triangulation (which is not necessarily delaunay). You are totally right that these inputs may not have a possible delaunay triangulation, but they will always have possible constrained delaunay triangulations! $\endgroup$
    – zaloo
    Jul 25, 2014 at 17:16
  • $\begingroup$ So I got confused. Are you looking for just triangulation? (according to your constrains, let call it constrained triangulation). If this is the case then I'd suggest to remove word delaunay from question body and title. Because x-delaunay-triangulation has very solid meaning, and it doesn't mean just triangulation (with your x-constrains). $\endgroup$
    – Saeed
    Jul 25, 2014 at 22:28

1 Answer 1

Reset to default
1
$\begingroup$

I think only those vertices corresponding to triangles sharing an edge with boundary or holes of the polygon will be of degree less than 3. Now the number of triangles in the triangulation is fixed. So you can always get the exact ratio of the number of degree 3 vertices for a polygon.

If the polygon has $k$ vertices and $l$ holes vertices and the number of triangles in the total triangulation is $N$ then the upper bound should be $(N-K-l)/N$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes but I believe N might be dependent on k and l, so we may be able to say more $\endgroup$
    – zaloo
    Feb 22, 2014 at 15:01
  • $\begingroup$ For $p$ points the total number of triangles are $2p-2-k$ triangles where $k$ is the number of points on the convex hull.In your case, it seems from the image that $k=4$. And for each hole you have two triangles. So the expression for total number of triangles becomes i think $N=2*p-6-2*h$. Each hole again has only 4 boundaries so, the ratio now becomes $(2*p-10-6*h)/(2*p-6-2*h)$. $\endgroup$
    – Dibyayan
    Feb 22, 2014 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.