Fortune's algorithm and circle as sweep line
I think it is possible to formulate Fortune's-like algorithm, but using circle instead of straight line as sweep line.
Say, "circle event" remains "circle event" and point event definition will slightly changed.
What also changed is binary tree implementation, but slightly. It became "binary tree mod 2 * pi" in some sense.
Parabolas from the original algorithm's wording are ellipses with one of two foci moved to infinity from their directrixes and so on similarly.
Are there any impediments for reformulation the algorithm definition in terms of circles and polar coordinates? Can it be generalized to higher dimensions?
N.B.: metric is sqrt(x * x + y * y).
ADDITIONAL:
I tried to infer equation for equidistant points from circle and the point that lies inside the circle. For point (a, 0) and circle center = (0, 0), radius = r the formula is rho = (r * r - a * a) / (2 * (r - a * cos(theta))). According to Wikipedia's article about ellipse the form of this inffered equation matches form of ellipse equation in polar coordinates relative to focus. Plot (slightly warped) visually demostrates correctness of this my conclusion:
For a == r (point lies on beach line) this ellipse becames (degenerates to) a line segment or, equally, radius, similar to corresponding ray from "point event" of original Fortune's algorithm wording.
There are two papers that I know of which describe a sweep circle approach to compute a Voronoi diagram in 2D. The second one "Parallel computing 2D VD..." also shows benchmarking results of their implementation. Unfortunately no link to a source code is provided, if you are looking for something like this.
- Is the inorder predecessor of a node with no left subtree and being the left child of its parent always its grandparent?
- How to calculate rounded corners for a polygon?
- Is the Inorder Predecessor of a Node with a Left Subtree Always a Leaf Node in a Binary Search Tree?
- Codility Leader Algorithm in JavaScript
- Tricky Google interview question
- Java problem time limit exceeded issue
- Can we get a better complexity than O(n) for cumulative sum while using multithreading?
- Fastest method to define whether a number is a triangular number
- What is a plain English explanation of "Big O" notation?
- How can I get the length of repeating decimal?
- Splitting dag dependencies in python
- How to find the time comlexity when comparing sublists?
- Clarification on `length = prefixTable[length - 1]` vs. `length = length - 1` in the KMP Algorithm
- Swapping two numbers using only two variables
- Fastest way to fill an array with a single value
- Algorithm for minimizing the amount of lines to draw?
- Convert Excel Column Number to Column Name in Matlab
- Find n-element in sequence. How to speed up the programm (time) for n > 10^6?
- O(n log n) algorithm to find number of large inversions
- Algorithm for drawing lines with 90-degree angles
- Depth First Search v.s. Greedy Best First Search
- How to improve pandas DF processing time on different combinations of calculated data
- How to speed up search in a huge dictionary
- Gradient Of Bezier Curve At Given Point
- How many ways can I choose numbers (repeatable) from a set that amount to the same sum?
- How can building a heap be O(n) time complexity?
- What is the reason why std::rotate() is implemented this way?
- String to string compression algorithm?
- Computing index from timestamp
- Forward chaining and Backward chaining in java