Questions tagged [delaunay-triangulation]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
370 views

Strongly edge-guarding a 3d triangulation

Let $T$ be a planar triangulation. It is known that one can guard the faces of $T$ using at most $\lfloor n/3 \rfloor$ edge-guards (Worst-case-optimal algorithms for guarding planar graphs and ...
4
votes
0answers
196 views

Triangulation with maximum greatest area

Given a point set $P$ and a triangulation $T$ of $P$ with $d$ triangles, let's define $$\alpha(T) = (\alpha_1, \alpha_2, \ldots, \alpha_{3d})$$ which denotes the series of interior angles of $T$, ...
3
votes
0answers
57 views

Voronoi diagrams applications where the input order has some known properties?

Are there applications of Voronoi diagrams or Delaunay triangulations where the order in which the points are generated (and given to the algorithm) have some known properties (e.g. concatenation of ...
2
votes
0answers
1k views

Maximum number of triangles in a constrained delaunay triangulation

I'm looking for an upper bound for the number of triangles in a constrained planar delaunay triangulation. I know for d=2 delaunay triangulation, there are at most n+1 triangles where n is the number ...
2
votes
0answers
108 views

Worst-case optimal Delaunay algorithm based on spatial sort and walking?

Buchin [2] showed that under "reasonable" assumptions, (polynomial point spread) incremental construction of Delaunay triangulations using the biased randomized ordering of Amenta et al. [1] with a ...
1
vote
0answers
29 views

Extending Delaunay graphs in d-space

I am new to computational geometry so pardon me for the lack of formalism. I am currently experimenting with an algorithm of mine in which I need to extend recursively a Delaunay graph in $d$-space. ...
1
vote
0answers
62 views

Partition planar graph of vertices with at most degree 3 into connected subgraphs

I'm currently working on my thesis which deals with pathfinding over a Delaunay triangulated graph. I want to be able to partition my Delaunay triangulation into disjoint (regarding vertices) ...
1
vote
0answers
53 views

Finding if an edge lies within a set of disjoint rectangles

I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside ...
0
votes
0answers
87 views

How many maximal planar graphs are there?

We denote by a triangulation a (simple) maximal planar graph. How many triangulations on $n$ vertices are there? How many triangulations are there if we cannot distinguish the vertices, i.e. ...
0
votes
0answers
438 views

Rectangular constraints in Delaunay Triangulation without edges within

I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside ...