December 14th, 2009, 06:58 AM  #1 
Newbie Joined: Feb 2009 Posts: 4 Thanks: 0  Distinct Triangulation
Find the number of distinct triangulations of the following polygons: a) Polygon P contain n+3 vertices V0=(0,0) V1=(1,0) ...Vn=(n,0) Vn+1=(1,1) and Vn+2=(0,1) labeled in the counterclockwise order. b)Polygon P contain n+4 vertices V0=(0,0) V1=(1,0) ...Vn=(n,0) Vn+1=(2,1) and Vn+2=(1,1) Vn+3=(0,1)labeled in the counterclockwise order. c)Polygon P contain n+5 vertices V0=(0,0) V1=(1,0) ...Vn=(n,0) Vn+1=(3,1) and Vn+2=(2,1) Vn+3=(1,1) Vn+4=(0, 1)labeled in the counterclockwise order. Note that 
December 15th, 2009, 01:08 PM  #2 
Member Joined: Oct 2009 Posts: 64 Thanks: 0  Re: Distinct Triangulation
You want to count up the number of nondegenerate triangles, I take it. This means you want the number of ways to choose a set of three noncollinear points. In cases a, b, and c, the set of points are arranged on one of either two parallel lines: y=0 or y=1. So the only way to get three collinear points is to have them all be on the same line. So count up the number of ways to choose a set of three points, and subtract off the number of ways to choose points either all on the line y=0 or all on the line y=1, and you have the number of ways to choose a set of three points which are not collinear. 

Tags 
distinct, triangulation 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Building a convex polygon map from triangulation  PanCotzky  Algebra  0  October 6th, 2012 12:39 PM 
Ordered distribution of distinct objects into distinct conta  metamath101  Algebra  2  June 22nd, 2012 05:59 PM 
Calculating Error metric (Restricted quadtree triangulation)  Hangout  Applied Math  0  April 17th, 2012 07:40 AM 
Can someone explain how to do stereo triangulation please?  johnnyleeftw  Applied Math  0  April 12th, 2010 12:45 PM 
Distinct triangulation  tinng  Algebra  0  December 14th, 2009 06:55 AM 