Article | SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden | Computation of Topologic Events in Kinetic Delaunay Triangulation using Sturm Sequences of Polynomials

Title:
Computation of Topologic Events in Kinetic Delaunay Triangulation using Sturm Sequences of Polynomials
Author:
Tomáš Vomácka: University of West Bohemia, Czech Republic Ivana Kolingerová: University of West Bohemia, Czech Republic
Download:
Full text (pdf)
Year:
2008
Conference:
SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden
Issue:
034
Article no.:
014
Pages:
57-64
No. of pages:
8
Publication type:
Abstract and Fulltext
Published:
2008-11-27
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press; Linköpings universitet


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

Keywords: Kinetic Delaunay Triangulation; Polynomial; Sturm Sequence

SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden

Author:
Tomáš Vomácka, Ivana Kolingerová
Title:
Computation of Topologic Events in Kinetic Delaunay Triangulation using Sturm Sequences of Polynomials
References:

ALBERS; G.; GUIBAS; L. J.; MITCHELL; J. S. B.; AND ROOS; T. 1998. Voronoi diagrams of moving points. International Journal of Computational Geometry and Applications 8; 3; 365–380.


DE BERG; M.; VAN KREVELD; M.; OVERMARS; M.; AND SCHWARZKOPF; O. 1997. Computational geometry: algorithms and applications. Springer-Verlag New York; Inc.; Secaucus; NJ; USA.


DEVILLERS; O. 1999. On deletion in delaunay triangulations. In Symposium on Computational Geometry; 181–188.


FERREZ; J.-A. 2001. Dynamic Triangulations for Efficient 3D Simulation of Granular Materials. PhD thesis; cole Polytechnique Fdrale De Lausanne.


GAVRILOVA; M.; ROKNE; J.; AND GAVRILOV; D. 1996. Dynamic collision detection in computational geometry. In 12th European Workshop on Computational Geometry; 103–106.


GOLD; C. M.; AND CONDAL; A. R. 1995. A spatial data structure integrating GIS and simulation in a marine environment. Marine Geodesy 18; 213–228.


HJELLE; O.; AND DÆHLEN; M. 2006. Triangulations and Applications. Berlin Heidelberg: Springer.


MOSTAFAVI; M. A.; GOLD; C.; AND DAKOWICZ; M. 2003. Delete and insert operations in Voronoi/Delaunay methods and applications. Comput. Geosci. 29; 4; 523–530.


PAN; V. Y. 1997. Solving a polynomial equation: Some history and recent progress. SIAM Review 39; 2 (June); 187–220.


PUNCMAN; P. 2008. Pou?zit´i triangulac´i pro reprezentaci videa; Diplomov´a pr´ace. University of West Bohemia; Pilsen; Czech Republic.


RALSTON; A. 1965. A First Course in Numerical Analysis. McGraw-Hill; Inc.: New York.


SCHALLER; G.; AND MEYER-HERMANN; M. 2004. Kinetic and dynamic delaunay tetrahedralizations in three dimensions. Computer Physics Communications 162; 9.


THIBAULT; D.; AND GOLD; C. M. 2000. Terrain reconstruction from contours by skeleton construction. Geoinformatica 4; 4; 349–373.


VOM´A ?C KA; T. 2008. Delaunay triangulation of moving points. In Proceedings of the 12th Central European Seminar on Computer Graphics; 67–74.


VOM´A ?C KA; T. 2008. Delaunay Triangulation of Moving Points in a Plane; Diploma Thesis. University of West Bohemia; Pilsen; Czech Republic. VOM´A ?C


KA; T. 2008. Use of delaunay triangulation of moving points as a data structure for video representation. Tech. rep.; University of WestBohemia; Pilsen; Czech Republic.


WEISSTEIN; E. W.; 2004. Fundamental theorem of algebra. From MathWorld - A Wolfram Web Resource. http://mathworld.wolfram.com/QuarticEquation.html.

SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden

Author:
Tomáš Vomácka, Ivana Kolingerová
Title:
Computation of Topologic Events in Kinetic Delaunay Triangulation using Sturm Sequences of Polynomials
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment