Tomáš Vomácka
University of West Bohemia, Czech Republic
Ivana Kolingerová
University of West Bohemia, Czech Republic
Ladda ner artikel
Ingår i: SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden
Linköping Electronic Conference Proceedings 34:14, s. 57-64
Publicerad: 2008-11-27
ISBN:
ISSN: 1650-3686 (tryckt), 1650-3740 (online)
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
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.
