6
votes
What edges are not in a Gabriel graph, yet in a Delauney graph?
Ah, I think I figured it out, thanks to the help from Discrete Lizard.
See the following image of a Delaunay triangulation, where I've highlighted one example where the edges would be included in DT, ...
- 123
4
votes
Accepted
Voronoi Cell and Voronoi Diagram
Let us assume that $P$ is in general position (no three points colinear, no four points cocircular) to make things easier.
As the Voronoi diagram is the dual of the Delaunay triangulation, this is ...
- 2,522
4
votes
Algorithm for farthest point Voronoi diagram?
There are linear-time algorithms to construct a farthest-point Voronoi diagram given a sorted list of vertices of a convex polygon. For a general set of points, first computing the convex hull results ...
- 2,348
3
votes
Voronoi Diagram Drawing Variations and Charateristics
The Voronoi diagram of disjoint segments (b) has been thoroughly studied.
Image from GIS.
See:
CGAL Manual, Chapter 43:
...
- 854
2
votes
Delaunay to Voronoi ... and back?
Unfortunately, you cannot generally reconstruct the generators from Voronoi polygons. Look at the four simple examples below: all have the same two Voronoi cells but different placement of the ...
- 146
2
votes
Compare two atan2
The following answer is based on the following graph, taken from Wikipedia:
If $x_i,x_j > 0$ then you can use the monotonicity of the arctangent to get the equivalent condition $y_i/x_i < y_j/...
- 277k
2
votes
Algorithm for farthest point Voronoi diagram?
It's published in Journal of Computational Geometry: Theory and
Applications, DOI 10.1016/j.comgeo.2010.11.004 by Cheong, Otfried and Everett, Hazel and Glisse, Marc and Gudmundsson, Joachim and ...
- 16.1k
2
votes
Accepted
What edges are not in a Gabriel graph, yet in a Delauney graph?
From my answer to a similar question:
A Delaunay edge $(x,y)$ won't be a Gabriel edge, if the set of all the possible empty disks with $x$ and $y$ on their boundaries doesn't contain the disk with ...
- 3,088
2
votes
Accepted
Voronoi Diagram: Exactly 2n-5 vertices
You made a small mistake by thinking that the Voronoi diagram is a planar graph. Remember that it has those rays that go to infinity. you can make a planar graph out of the Voronoi diagram by adding a ...
- 12.2k
1
vote
Accepted
Is Fortune's algorithms for Voronoi diagrams described anywhere by Prof. Fortune?
The "popular description" of Fortune's algorithm in terms of parabolas does not appear to be due to Fortune, but due to Guibas and Stolfi [1]. They start by analyzing the geometrical ...
- 8,248
1
vote
Accepted
Nearest Neighbour search with Kirkpatrick's Hierarchy and Re-Triangulating Delaunay after vertex removal
To make our life easier, we always assume that the convex hull of the triangulation consists of three points. If it is not, just add three points far away and triangulate. Then, the important thing is ...
- 26
1
vote
Can breakpoints of the beachline move up in Fortune's algorithm?
Consider a situation where the sweep line is just below a site q, whose arc intersects arcs corresponding to the same site p on both ends:
- 11
1
vote
Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time
If you have a voronoi diagram you have neighbour information of each $p$. You can use that to path search (using A* or even greedy depth first) to the 3 points that surround $q$. Then you can extract ...
- 4,406
1
vote
Robot swarm, Maximum area coverage
I assume by "comparable part of the area" you mean that they should all scan a region of equal area. Additionally, knowing what kind of plane area you have would be helpful, is it convex, is it ...
- 59
1
vote
Is every planar graph a possible dual graph of a voronoi diagram?
No. The dual graph of a Voronoi diagram is the Delaunay triangulation of its point set so, in particular, every interior face of it is a triangle. But there are plenty of planar graphs (e.g., the $4$-...
- 81.7k
1
vote
Accepted
Finding the Voronoi cell a point belongs to
I will consider this problem on a Voronoi diagram with $n$ sites and $m$ query points.
Generally, trapezoidal decompositions work nicely for point-location. However, as we here have a subdivision of ...
- 8,248
1
vote
Compare two atan2
Just to summarize the answer above as a computer programme (the determinant method does not work):
...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible