Voronoi cells in metric algebraic geometry of plane curves
DOI:
https://doi.org/10.7146/math.scand.a-139875Abstract
Voronoi cells of varieties encode many features of their metric geometry. We prove that each Voronoi or Delaunay cell of a plane curve appears as the limit of a sequence of cells obtained from point samples of the curve. We use this result to study metric features of plane curves, including the medial axis, curvature, evolute, bottlenecks, and reach. In each case, we provide algebraic equations defining the object and, where possible, give formulas for the degrees of these algebraic varieties. We show how to identify the desired metric feature from Voronoi or Delaunay cells, and therefore how to approximate it by a finite point sample from the variety.
References
Victoria school districts, http://melbourneschoolzones.com/.
Aamari, E., Chazal, F., Kim, J., Michel, B., Rinaldo, A., and Wasserman, L., Estimating the reach of a manifold, Electron. J. Statist. 13 (2019), no. 1, 1359–1399. https://doi.org/10.1214/19-ejs1551
Alliez, P., Cohen-Steiner, D., Tong, Y., and Desbrun, M., Voronoi-based variational reconstruction of unoriented point sets, in “Proceedings of the Fifth Eurographics Symposium on Geometry Processing” (Aire-la-Ville, Switzerland), SGP '07, Eurographics Association, 2007, pp. 39–48.
Amenta, N., and Bern, M., Surface reconstruction by Voronoi filtering, 14th Annual ACM Symposium on Computational Geometry (Minneapolis, MN, 1998). Discrete Comput. Geom. 22 (1999), no. 4, 481–504, https://doi.org/10.1007/PL00009475
Attali, D., Boissonnat, J.-D., and Edelsbrunner, H., Stability and computation of medial axes: a state-of-the-art report, Mathematical foundations of scientific visualization, computer graphics, and massive data exploration, 109–125, Math. Vis., Springer, Berlin, 2009. https://doi.org/10.1007/b106657_6
Brandt, J. W., Convergence and continuity criteria for discrete approximations of the continuous planar skeleton, CVGIP: Image Understanding 59 (1994), no. 1, 116–124. https://doi.org/https://doi.org/10.1006/ciun.1994.1007
Brandt, J. W. and Algazi, V. R., Continuous skeleton computation by Voronoi diagram, CVGIP: Image Understanding 55 (1992), no. 3, 329–338. https://doi.org/https://doi.org/10.1016/1049-9660(92)90030-7
Breiding, P., Kališnik, S., Sturmfels, B., and Weinstein, M., Learning algebraic varieties from samples, Rev. Mat. Complut. 31 (2018), no. 3, 545–593. https://doi.org/10.1007/s13163-018-0273-6
Breiding, P., and Timme, S., The reach of a plane curve, https://www.JuliaHomotopyContinuation.org/examples/reach-curve/ , Accessed: March 10, 2023.
Breiding, P., and Timme, S., Homotopycontinuation.jl: A package for homotopy continuation in Julia, in “Mathematical Software–ICMS 2018” (Cham) (Davenport, J. H., Kauers, M., Labahn, G., and Urban, J., eds.), Springer International Publishing, 2018, pp. 458–465.
Cifuentes, D., Ranestad, K., Sturmfels, B., and Weinstein, M., Voronoi cells of varieties, J. Symbolic Comput. 109 (2022), 351–366. https://doi.org/10.1016/j.jsc.2020.07.009
Ciripoi, D., Kaihnsa, N., Löhne, A., and Sturmfels, B., Computing convex hulls of trajectories, Rev. Un. Mat. Argentina 60 (2019), no. 2, 637–662. https://doi.org/10.33044/revuma.v60n2a22
Cohen-Steiner, D., and Morvan, J.-M., Restricted Delaunay triangulations and normal cycle, in “Proceedings of the Nineteenth Annual Symposium on Computational Geometry” (New York, NY, USA), SCG '03, ACM, 2003, pp. 312–321. https://doi.org/10.1145/777792.777839
Dey, T. K., and Zhao, W., Approximate medial axis as a Voronoi subcomplex, in “Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications” (New York, NY, USA), SMA '02, ACM, 2002, pp. 356–366. https://doi.org/10.1145/566282.566333
Di Rocco, S., Eklund, D., and Weinstein, M., The bottleneck degree of algebraic varieties, SIAM J. Appl. Algebra Geom. 4 (2020), no. 1, 227–253. https://doi.org/10.1137/19M1265776
Draisma, J., Horobeţ, E., Ottaviani, G., Sturmfels, B., and Thomas, R. R., The Euclidean distance degree of an algebraic variety, Found. Comput. Math. 16 (2016), no. 1, 99–149. https://doi.org/10.1007/s10208-014-9240-x
Eklund, D., The numerical algebraic geometry of bottlenecks, Adv. in Appl. Math. 142 (2023), Paper No. 102416, 20pp. https://doi.org/10.1016/j.aam.2022.102416
Federer, H., Curvature measures, Trans. Amer. Math. Soc. 93 (1959), 418–491. https://doi.org/10.2307/1993504
Fuchs, D., and Tabachnikov, S., Mathematical omnibus: Thirty lectures on classic mathematics, American Mathematical Society, Providence, RI, 2007. https://doi.org/10.1090/mbk/046
Giblin, P. J., and Kimia, B. B., On the local form and transitions of symmetry sets, medial axes, and shocks, International Journal of Computer Vision 54 (2003), no. 1, 143–157. https://doi.org/10.1023/A:1023761518825
Grayson, D. R., and Stillman, M. E., Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2/.
Joswig, M., and Theobald, T., Polyhedral and algebraic methods in computational geometry, Universitext, Springer, London, 2013. https://doi.org/10.1007/978-1-4471-4817-3
Matheron, G., Random sets and integral geometry., Wiley series in probability and mathematical statistics, John Wiley & Sons, New York-London-Sydney, 1975
Merigot, Q., Ovsjanikov, M., and Guibas, L. J., Voronoi-based curvature and feature estimation from point clouds, IEEE Transactions on Visualization and Computer Graphics 17 (2011), no. 6, 743–756. https://doi.org/10.1109/TVCG.2010.261
Niyogi, P., Smale, S., and Weinberger, S., Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom. 39 (2008), no. 1-3, 419–441. https://doi.org/10.1007/s00454-008-9053-2
Salmon, G., A treatise on conic sections containing an account of some important algebraic and geometric methods, Hodges and Smith, 1848.
Salmon, G., A treatise on the higher plane curves, third ed., Hodges, Foster, and Figgis, 1879.
Scholtes, S., On hypersurfaces of positive reach, alternating Steiner formulae and Hadwiger's Problem, arXiv:1304.4179.
