9/11/2023 0 Comments Voronoi setIn $R^2$, the bisectors are just parabola segments and there is no need to handle surfaces in $R^3$ and their intersection curves. However, the problem in $R^2$ is relatively easy compared to the 3D problem in your question. The VRONI implementation, on the other hand, uses a more engineering approach for floating point computations, which combines the relaxation of epsilon thresholds with a multi-level recovery process.īoth implementations are very impressive in their achievement. The CGAL implementation adopts the Exact Geometric Computation (EGC) paradigm (including exact computations with square roots) and applies advanced geometric and arithmetic filtering for acceleration. The book " Effective Computational Geometry for Curves and Surfaces" presents some of these methods for many known problems and in the context of your question, chapter 2 is especially relevant and can refer you to additional papers.Įven for the limited case of line segments in $R^2$, the two excellent implementations you cited apply advanced methods to handle these problems. Handling these degenerate cases in general and for curved objects, in particular, requires both theoretical and practical sophisticated methods. ![]() With many papers presenting problems even for simpler objects such as points and lines (for example, this one). Robustness issues in geometric computing are a known research problem (see, for example, here, here or here), However, moving from Voronoi diagrams of points to diagrams of more complicated objects shifts the difficulty from asymptotical complexity issues (i.e., devising asymptotically efficient algorithms for point sets) to the difficulty of representing and computing with curved bisectors.įurthermore, implementing algorithms that work on curved bisectors encounters inherent robustness difficulties.Īs an example, the vertex of a 3D Voronoi diagram is, by definition, a single intersection point of four edge curves in $R^3$, or equivalently of six face surfaces. ![]() This has not always been the case, so it still isn't trivial. Voronoi diagrams of points in $R^3$ are now implemented in several software libraries and can be computed, for example, in a few lines of Python code.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |