Continuous and Discrete Radius Functions on Voronoi Tessellations and Delaunay Mosaics
Tóm tắt
The Voronoi tessellation in
$${{{\mathbb {R}}}}^d$$
is defined by locally minimizing the power distance to given weighted points. Symmetrically, the Delaunay mosaic can be defined by locally maximizing the negative power distance to other such points. We prove that the average of the two piecewise quadratic functions is piecewise linear, and that all three functions have the same critical points and values. Discretizing the two piecewise quadratic functions, we get the alpha shapes as sublevel sets of the discrete function on the Delaunay mosaic, and analogous shapes as superlevel sets of the discrete function on the Voronoi tessellation. For the same non-critical value, the corresponding shapes are disjoint, separated by a narrow channel that contains no critical points but the entire level set of the piecewise linear function.
Tài liệu tham khảo
Bauer, U., Edelsbrunner, H.: The Morse theory of Čech and Delaunay complexes. Trans. Am. Math. Soc. 369(5), 3741–3762 (2017)
Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Extending persistence using Poincaré and Lefschetz duality. Found. Comput. Math. 9(1), 79–103 (2009)
Cohen-Steiner, D., Edelsbrunner, H., Morozov, D.: Vines and vineyards by updating persistence in linear time. In: 22nd Annual Symposium on Computational Geometry (Sedona 2006), pp. 119–126. ACM, New York (2006)
Delaunay, B.: Sur la sphère vide. Izv. Akad. Nauk SSSR, Otdelenie Mat. Est. Nauk 1934(6), 793–800 (1934)
Edelsbrunner, H.: The union of balls and its dual shape. Discrete Comput. Geom. 13(3–4), 415–440 (1995)
Edelsbrunner, H.: Surface reconstruction by wrapping finite sets in space. In: Discrete and Computational Geometry. The Goodman–Pollack Festschrift. Algorithms Combin., vol. 25, pp. 379–404. Springer, Berlin (2003)
Edelsbrunner, H., Kirkpatrick, D.G., Seidel, R.: On the shape of a set of points in the plane. IEEE Trans. Inform. Theory 29(4), 551–559 (1983)
Edelsbrunner, H., Koehl, P.: The geometry of biomolecular solvation. In: Combinatorial and Computational Geometry. Math. Sci. Res. Inst. Publ., vol. 52, pp. 243–275. Cambridge University Press, Cambridge (2005)
Edelsbrunner, H., Mücke, E.P.: Three-dimensional alpha shapes. ACM Trans. Graphics 13(1), 43–72 (1994)
Forman, R.: Morse theory for cell complexes. Adv. Math. 134(1), 90–145 (1998)
Forman, R.: A user’s guide to discrete Morse theory. Sém. Lothar. Combin. 48, # B48c (2002)
Freij, R.: Equivariant discrete Morse theory. Discrete Math. 309(12), 3821–3829 (2009)
Gardiner, J.D., Behnsen, J., Brassey, C.A.: Alpha shapes: determining 3D shape complexity across morphologically diverse structures. BMC Evolut. Biol. 18, # 184 (2018)
Krishan, K., Kurtuldu, H., Schatz, M., Gameiro, M., Mischaikow, K., Madruga, S.: Homology and symmetry breaking in Rayleigh–Bénard convection: experiments and simulations. Phys. Fluids 19, # 117105 (2007)
Lee, B., Richards, F.M.: The interpretation of protein structures: estimation of static accessibility. J. Mol. Biol. 55(3), 379–400 (1971)
Maddah, M.R., Cao, C.G.L.: Application of the alpha shape method to visualize and analyze surgical motions. Surg. Sci. 8(11), 464–480 (2017)
Milnor, J.: Morse Theory. Annals of Mathematics Studies, vol. 51. Princeton University Press, Princeton (1963)
Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Menlo Park (1984)
Pedoe, D.: Geometry: A Comprehensive Course. Dover Books on Advanced Mathematics. Dover, New York (1988)
Ramos, E.A., Sadri, B.: Geometric and topological guarantees for the WRAP reconstruction algorithm. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2007), pp. 1086–1095. ACM, New York (2007)
Voronoi, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire: recherches sur les parallélloèdres primitifs. J. Reine Angew. Math. 134, 198–287 (1908)
Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)