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. ===========================================================================