Konferensartikel

Even though the problem of maintaining the kinetic Delaunay triangulation is well known; this field of computational geometry leaves several problems unsolved. We especially aim our research at the area of computing the times of the topologic events. Our method uses the Sturm sequences of polynomials which; combined together with the knowledge in associated field of mathematics; allows us to separate the useful roots of the counted polynomial equations from those which are unneeded. Furthermore; we adress the problem of redundant event computation which consumes an indispensable amount of the runtime (almost 50% of the events is computed but not executed). Despite the deficiency in the fields of speed and stability of our current implementation of the algorithm; we show that a large performance enhancement is theoreticaly possible by recognizing and not computing the redundant topologic events.

CR Categories: G.1.5 [Numerical Analysis]: Roots of Nonlinear Equations—Polynomials; methods for; I.3.5 [Computer Graphics]: Computational Geometry and Object Modelling—Geometric algorithms; languages; and systems

Kinetic Delaunay Triangulation; Polynomial; Sturm Sequence