Questions tagged [delaunay-triangulation]
The delaunay-triangulation tag has no usage guidance.
21
questions
0
votes
0
answers
98
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. ...
- 1
1
vote
1
answer
89
views
Delaunay triangulation when some triangles have been pre-specified?
I have an implementation of the Bowyer-Watson algorithm for Delaunay triangulation which works well -- given a set of 2D points, it computes a set of triangles to fill the areas between the points.
...
- 111
-1
votes
1
answer
341
views
Example of Delaunay Triangulation where it does not minimize the maximum angle
I know that that the Delaunay triangulation maximizes the minimum angle of triangulation.
And it does not minimize the maximum angle. If we consider the set of points in general position(no four ...
- 1,531
4
votes
1
answer
122
views
Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm
Roughly speaking, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain.
The algorithm specifies splitting the edges ...
- 235
1
vote
0
answers
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.
...
- 173
5
votes
1
answer
130
views
Topological properties of Delaunay triangulations
Do Delaunay triangulations satisfy any extra topological conditions over normal planar triangulations?
In other words, if $T$ is a topological triangulation of the plane, when does there exist points ...
- 3,243
2
votes
0
answers
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 ...
- 383
0
votes
1
answer
869
views
Number of "3-edge" triangles in a planar triangulation
I'm working on a triangle partitioning problem, and I'm trying to find and prove some properties of specific triangulations. The triangulations I'm dealing with are constrained delaunay triangulations ...
- 383
8
votes
4
answers
2k
views
Partitioning graphs while minimizing inter-partition edges
I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been ...
- 383
1
vote
0
answers
118
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 ...
- 3,243
1
vote
0
answers
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) ...
- 383
0
votes
0
answers
511
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 ...
- 383
1
vote
0
answers
56
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 ...
- 383
4
votes
2
answers
346
views
Properties about verticies in Delaunay Triangulations
I'm working on my thesis dealing with pathfinding over Delaunay triangulations. I have an algorithm that has running time in time proportional to the degree of a vertex. Are there any properties or ...
- 383
1
vote
1
answer
214
views
Delaunay Triangulation of Parallelepiped
Given $n$ linearly independent vectors $v_1, v_2, \ldots, v_n$ in $n$-dimensional space. Let $V$ be the set of $2^n$ points of the form $x_1 v_1 + x_2v_2 + \ldots + x_nv_n$, in which $x_i$ can be $0$ ...
- 53
3
votes
0
answers
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,733
5
votes
0
answers
373
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 ...
user183
9
votes
1
answer
2k
views
What is the worst case of the randomized incremental delaunay triangulation algorithm?
I know that the expected worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in Computational Geometry) is $\mathcal O(n \log n)$.
There is an exercise which ...
- 193
4
votes
0
answers
233
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$, ...
6
votes
3
answers
497
views
How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?
I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring ...
- 177
9
votes
1
answer
708
views
Do Delaunay triangulations on the sphere maximize the minimum angle?
Delaunay triangulations in the plane maximize the minimum angle in a triangle. Does the same hold true for the Delaunay triangulation of points on the sphere ? (here the "angle" is the local angle in ...
- 32k