Dynamic Comptational Geometry

The goal of this page is to demonstrate with video some concepts of computational geometry for dynamic sets with the hope that seeing structures in motion help grasp further more the concepts.

[Convex Hull] [Maximal Layer] [Smallest Enclosing Ball] [Voronoi Diagram] [Misc]

Convex hulls

Output-Sensitive Convex Hull Algorithms of Planar Convex Objects. Int. J. Comput. Geometry Appl. 8(1): 39-66 (1998)

[Convex Hull] [Maximal Layer] [Smallest Enclosing Ball] [Voronoi Diagram] [Misc]

Maximal and convex layers

Output-Sensitive Peeling of Convex and Maximal Layers. Inf. Process. Lett. 59(5): 255-259 (1996)

[Convex Hull] [Maximal Layer] [Smallest Enclosing Ball] [Voronoi Diagram] [Misc]

Smallest enclosing balls

Approximating Covering and Minimum Enclosing Balls in Hyperbolic Geometry. GSI 2015: 586-594
On approximating the Riemannian 1-center. Comput. Geom. 46(1): 93-104 (2013)
Approximating Smallest Enclosing Balls with Applications to Machine Learning. Int. J. Comput. Geometry Appl. 19(5): 389-414 (2009)
On the smallest enclosing information disk. Inf. Process. Lett. 105(3): 93-97 (2008)
On approximating the smallest enclosing Bregman Balls. Symposium on Computational Geometry 2006: 485-486
Fitting the Smallest Enclosing Bregman Ball. ECML 2005: 649-656
Approximating Smallest Enclosing Balls. ICCSA (3) 2004: 147-157

[Convex Hull] [Maximal Layer] [Smallest Enclosing Ball] [Voronoi Diagram] [Misc]

Voronoi diagrams/Delaunay triangulations

Visualizing hyperbolic Voronoi diagrams. Symposium on Computational Geometry 2014: 90
Further results on the hyperbolic Voronoi diagrams. CoRR abs/1410.1036 (2014)
The hyperbolic Voronoi diagram in arbitrary dimension. CoRR abs/1210.8234 (2012)
Skew Jensen-Bregman Voronoi Diagrams. Trans. Comput. Sci. 14: 102-128 (2011)
Bregman Voronoi Diagrams. Discret. Comput. Geom. 44(2): 281-307 (2010)
Hyperbolic Voronoi Diagrams Made Easy. ICCSA Workshops 2010: 74-80

Jensen-Bregman Voronoi Diagrams and Centroidal Tessellations. ISVD 2010: 56-65
The Dual Voronoi Diagrams with Respect to Representational Bregman Divergences. ISVD 2009: 71-78
Quantum Voronoi diagrams and Holevo channel capacity for 1-qubit quantum states. ISIT 2008: 96-100
Visualizing Bregman voronoi diagrams. Symposium on Computational Geometry 2007: 121-122
On Bregman Voronoi diagrams. SODA 2007: 746-755

[Convex Hull] [Maximal Layer] [Smallest Enclosing Ball] [Voronoi Diagram] [Misc]

Piercing (stabbing) and covering

Fast stabbing of boxes in high dimensions. Theor. Comput. Sci. 246(1-2): 53-72 (2000)
Maintenance of a Percing Set for Intervals with Applications. ISAAC 2000: 552-563
On Piercing Sets of Objects. Symposium on Computational Geometry 1996: 113-121