Triangulation

[Richard Guy]

It depends on the arrangement.  Suppose
that the convex hull of the  N  nodes
is a polygon with  b  boundary nodes,
and hence  b  edges.  Suppose that there
are  E  edges and  T  triangles.  Then

        2E  =  3T  +  b

and Euler tells us that

      N  +  (T+1)  =  E  +  2

Eliminate  E  to  give

       T  =  2N - b - 2

b  is at least 3  (in which case do you
count the boundary as a triangle of the
triangulation?), so the max is 2N - 5.

E.g., if  N = 4, you either have  b = 3
or  b = 4, i.e., a triangle with a node
and 3 triangles inside it, or a quadrangle
chopped into 2 triangles.  R.

On Mon, 17 Oct 2005, Pfoertner, Hugo wrote:

> SeqFans,
>
> my colleague Guido Dhondt just sent me the following question:
>
> -----Original Message-----
> From: 	Dhondt, Guido , Dr.
> Sent:	Monday, October 17, 2005 11:18
> To:	Pfoertner, Hugo
> Subject:	triangulation
>
>> What is the maximum number of triangles of a triangulation connecting N
> nodes in a plane?
>>
>> (needed as upper memory bound for triangulation in CalculiX,
> www.calculix.de)
>
> I tried to search OEIS for triangles & triangulation, triangles & maximal.
>
> http://www.research.att.com/projects/OEIS?Anum=A027610
>
> seems to be related (Number of chordal planar triangulations; also number of
> planar
> triangulations with maximal number of triangles; ....)
>
> Any hints?
>
> Hugo Pfoertner
>
> ===========================================================================
> REFERENCE of the administration: This E-Mail was delivered via InterNet.
> Unencrypted InterNet-E-Mails could be read or falsified by unauthorized
> persons.
> ---------------------------------------------------------------------------
> HINWEIS der Administration: Diese E-Mail wurde Ihnen ueber INTERNET
> zugestellt. Unverschluesselte Internet-E-Mails koennten von Unbefugten
> gelesen oder verfaelscht werden.
> ===========================================================================
>