13
$\begingroup$

A set of $n$ points in the plane in generic position (no alignement of three points) has at least $2.012^n$ different triangulations of its convex hull involving only the set of given points.We call such a triangulation a checkerboard-triangulation if every interior vertex belongs to an even number of triangles (ie. triangles can be colored black-white with adjacent triangles being of different colours, equivalently, vertices of a checkerboard-triangulation can be coloured using only three different colours). A "random" set of $n$ points is certainly in generic position and the parity of the degree of a fixed vertex in such a triangulation should be "random", ie. even for about half of all possible triangulations. Assuming independence of parities of degrees of different vertices, one should thus expect the existence of checkerboard-triangulations for large random configurations of points.

Otherwise stated, let $A_n$ be the number of combinatorially different sets of $n$ points in generic position (also called "order-types") and let $B_n$ be the number of such sets (up to combinatorial equivalence) which have a checkerboard-triangulation. Does $B_n/A_n$ tend to $1$? (Two configurations are combinatorially equivalent if they are isotopic in the set of generic configurations, endowed with the obvious topology).

Warning: There are arbitrarily large generic sets of points with no checkerboard triangulation: Take $(x_i,y_i)$ with $x_1=-1<x_2<\dots<x_n=1$ and $y_i=x_i^2-1$ and add $(x_{n+1},y_{n+1})=(0,-2)$. Every triangulation is obtained by joining the first $n$ points $(x_1,y_1),\dots,(x_n,y_n)$ to the last point $(0,-2)$ and by triangulation the convex hull of the first $n$ points. This leads always to the existence of a point of odd degree among $(x_2,y_2),\dots,(x_{n-1},y_{n-1})$.

$\endgroup$
1
  • 1
    $\begingroup$ What is the complexity to decide whether a given point set has a checkerboard triangulation? $\endgroup$
    – domotorp
    Feb 3, 2014 at 7:34

0

Your Answer

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

Browse other questions tagged or ask your own question.