On the Number of Higher Order Delaunay Triangulations

DOI10.1007/978-3-642-13073-1_20zbMATH Open1284.68612arXiv1002.4364OpenAlexW1648170231MaRDI QIDQ3563004FDOQ3563004

Authors: D. Mitsche, Maria Saumell, Rodrigo I. Silveira

Publication date: 28 May 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Higher order Delaunay triangulations are a generalization of the Delaunay triangulation which provides a class of well-shaped triangulations, over which extra criteria can be optimized. A triangulation is order-

k

Delaunay if the circumcircle of each triangle of the triangulation contains at most

k

points. In this paper we study lower and upper bounds on the number of higher order Delaunay triangulations, as well as their expected number for randomly distributed points. We show that arbitrarily large point sets can have a single higher order Delaunay triangulation, even for large orders, whereas for first order Delaunay triangulations, the maximum number is

2^{n - 3}

. Next we show that uniformly distributed points have an expected number of at least

2^{h o_{1} n (1 + o (1))}

first order Delaunay triangulations, where

h o_{1}

is an analytically defined constant (

h o_{1} a p p r o x 0.525785

), and for

k > 1

, the expected number of order-

k

Delaunay triangulations (which are not order-

i

for any

i < k

) is at least

2^{h o_{k} n (1 + o (1))}

, where

h o_{k}

can be calculated numerically.

Full work available at URL: https://arxiv.org/abs/1002.4364

Recommendations

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (15)

This page was built for publication: On the Number of Higher Order Delaunay Triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3563004)