Easiest algorithm of Voronoi diagram to implement? [closed]

by

An easy algorithm to compute the Delaunay triangulation of a point set is flipping edges. Since a Delaunay triangulation is the dual graph of a Voronoi diagram, you can construct the diagram from the triangulation in linear time.

Unfortunately, the worst case running time of the flipping approach is O(n^2). Better algorithms such as Fortune’s line sweep exist, which take O(n log n) time. This is somewhat tricky to implement though. If you’re lazy (as I am), I would suggest looking for an existing implementation of a Delaunay triangulation, use it, and then compute the dual graph.

In general, a good book on the topic is Computational Geometry by de Berg et al.

More Related Contents:

  1. Algorithm to beat Strassen’s Algorithm
  2. HSL to RGB color conversion
  3. Constant Amortized Time
  4. What exactly does big Ө notation represent?
  5. Select k random elements from a list whose elements have weights
  6. How are ssl certificates verified?
  7. How to find the intersection point between a line and a rectangle?
  8. What is the difference between tree depth and height?
  9. What would cause an algorithm to have O(log n) complexity?
  10. Finding the median of an unsorted array
  11. How to estimate download time remaining (accurately)?
  12. Sorting in linear time? [closed]
  13. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  14. median of three values strategy
  15. Fast Algorithm to Quickly Find the Range a Number Belongs to in a Set of Ranges?
  16. How to compute a 3D Morton number (interleave the bits of 3 ints)
  17. Fastest algorithm for circle shift N sized array for M position
  18. Lights out game algorithm
  19. How does this work? Weird Towers of Hanoi Solution
  20. Reverse complex 2D lookup table
  21. JavaScript: Calculate the nth root of a number
  22. Generating shuffled range using a PRNG rather than shuffling
  23. Find out which combinations of numbers in a set add up to a given total
  24. Print the biggest K elements in a given heap in O(K*log(K))?
  25. Variation on knapsack – minimum total value exceeding ‘W’
  26. Path generation for non-intersecting disc movement on a plane
  27. How can I perform Collision Detection on rotated rectangles? [closed]
  28. Find the pair across 2 arrays with kth largest sum
  29. algorithm to check a connect four field
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment