The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
84 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 ...
0
votes
0answers
21 views

Whether no local degeneracy in PLC implies edge-protection?

In a paper on Constrained Delaunay tetrahedralization (Meshing Piecewise linear complexes with Constrained Delaunay tetrahedralizations), in section 3, in proof of theorem 2, author claims that if ...
0
votes
0answers
46 views

What is the intuition behind Steiner point insertion rules?

I am reading a paper on Constrained Delaunay tetrahedralization (Meshing Piecewise linear complexes with Constrained Delaunay tetrahedralizations). It mentions rules for inserting steiner points but ...
0
votes
0answers
134 views

A* in triangulated search space

I have a question regarding the optimality of a specific A* in triangulated search spaces (planar). Suppose I have some convex polygon (the boundary) with some number of obstacles (other convex ...
2
votes
0answers
107 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 ...
0
votes
1answer
319 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 ...
7
votes
4answers
383 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 ...
2
votes
0answers
50 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
43 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) ...
0
votes
0answers
72 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 ...
1
vote
0answers
46 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 ...
5
votes
2answers
98 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 ...
1
vote
1answer
112 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$ ...
3
votes
0answers
48 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 ...
5
votes
0answers
321 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
385 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
154 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
436 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
477 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 ...