The delaunay-triangulation tag has no wiki summary.
5
votes
0answers
267 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 ...
9
votes
1answer
156 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 ...
4
votes
0answers
119 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
3answers
395 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 ...
9
votes
1answer
401 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 ...
