{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T23:04:40Z","timestamp":1768863880426,"version":"3.49.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,3,1]],"date-time":"2020-03-01T00:00:00Z","timestamp":1583020800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T00:00:00Z","timestamp":1583280000000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Institute of Science and Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Coxeter triangulations are triangulations of Euclidean space based on a single simplex. By this we mean that given an individual simplex we can recover the entire triangulation of Euclidean space by inductively reflecting in the faces of the simplex. In this paper we establish that the quality of the simplices in all Coxeter triangulations is <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(1\/\\sqrt{d})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>\/<\/mml:mo><mml:msqrt><mml:mi>d<\/mml:mi><\/mml:msqrt><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the quality of regular simplex. We further investigate the Delaunay property for these triangulations. Moreover, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(1\/d^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>\/<\/mml:mo><mml:msup><mml:mi>d<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We conjecture that both bounds are optimal for triangulations in Euclidean space.<\/jats:p>","DOI":"10.1007\/s11786-020-00461-5","type":"journal-article","created":{"date-parts":[[2020,3,4]],"date-time":"2020-03-04T12:03:06Z","timestamp":1583323386000},"page":"141-176","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Coxeter Triangulations Have Good Quality"],"prefix":"10.1007","volume":"14","author":[{"given":"Aruni","family":"Choudhary","sequence":"first","affiliation":[]},{"given":"Siargey","family":"Kachanovich","sequence":"additional","affiliation":[]},{"given":"Mathijs","family":"Wintraecken","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,4]]},"reference":[{"key":"461_CR1","doi-asserted-by":"crossref","unstructured":"Adams, A., Baek, J., Davis, M.A.: Fast high-dimensional filtering using the permutohedral lattice. In: Computer Graphics Forum, vol. 29, pp. 753\u2013762. Wiley Online Library (2010)","DOI":"10.1111\/j.1467-8659.2009.01645.x"},{"issue":"2","key":"461_CR2","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0713021","volume":"13","author":"I Babu\u0161ka","year":"1976","unstructured":"Babu\u0161ka, I., Aziz, A.K.: On the angle condition in the finite element method. SIAM J. Numer. Anal. 13(2), 214\u2013226 (1976)","journal-title":"SIAM J. Numer. Anal."},{"key":"461_CR3","doi-asserted-by":"publisher","unstructured":"Bogdanov, M., Teillaud, M., Vegter, G.: Delaunay triangulations on orientable surfaces of low genus. In: Proceedings of the Thirty-Second International Symposium on Computational Geometry, pp. 20:1\u201320:17 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2016.20. https:\/\/hal.inria.fr\/hal-01276386","DOI":"10.4230\/LIPIcs.SoCG.2016.20"},{"issue":"4\u20135","key":"461_CR4","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1142\/S0218195913600078","volume":"23","author":"JD Boissonnat","year":"2013","unstructured":"Boissonnat, J.D., Dyer, R., Ghosh, A.: The stability of delaunay triangulations. Int. J. Comput. Geom. Appl. 23(4\u20135), 303\u2013334 (2013). https:\/\/doi.org\/10.1142\/S0218195913600078","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"02","key":"461_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1142\/S021819591450006X","volume":"24","author":"JD Boissonnat","year":"2014","unstructured":"Boissonnat, J.D., Dyer, R., Ghosh, A.: Delaunay stability via perturbations. Int. J. Comput. Geom. Appl. 24(02), 125\u2013152 (2014)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"461_CR6","doi-asserted-by":"publisher","unstructured":"Boissonnat, J.D., Dyer, R., Ghosh, A.: A probabilistic approach to reducing algebraic complexity of delaunay triangulations. In: Proceedings of Algorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, pp. 595\u2013606 (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_50","DOI":"10.1007\/978-3-662-48350-3_50"},{"key":"461_CR7","doi-asserted-by":"crossref","unstructured":"Bourbaki, N.: Lie groups and Lie algebras. In: Chapters 4\u20136. Translated from the 1968 French original by Andrew Pressley. Elements of Mathematics (2002)","DOI":"10.1007\/978-3-540-89394-3"},{"issue":"2","key":"461_CR8","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1002\/nme.1620210210","volume":"21","author":"JC Cavendish","year":"1985","unstructured":"Cavendish, J.C., Field, D.A., Frey, W.H.: An apporach to automatic three-dimensional finite element mesh generation. Int. J. Numer. Methods Eng. 21(2), 329\u2013347 (1985). https:\/\/doi.org\/10.1002\/nme.1620210210","journal-title":"Int. J. Numer. Methods Eng."},{"key":"461_CR9","first-page":"1018","volume":"5","author":"SW Cheng","year":"2005","unstructured":"Cheng, S.W., Dey, T.K., Ramos, E.A.: Manifold reconstruction from point samples. SODA 5, 1018\u20131027 (2005)","journal-title":"Manifold reconstruction from point samples. SODA"},{"key":"461_CR10","volume-title":"Delaunay Mesh Generation","author":"SW Cheng","year":"2012","unstructured":"Cheng, S.W., Dey, T.K., Shewchuk, J.: Delaunay Mesh Generation. CRC Press, Boca Raton (2012)"},{"key":"461_CR11","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/s00454-017-9951-2","volume":"61","author":"A Choudhary","year":"2017","unstructured":"Choudhary, A., Kerber, M., Raghvendra, S.: Polynomial-sized topological approximations using the permutahedron. Discrete Comput. Geom. 61, 42\u201380 (2017)","journal-title":"Discrete Comput. Geom."},{"key":"461_CR12","volume-title":"Sphere-Packings, Lattices, and Groups","author":"JH Conway","year":"1987","unstructured":"Conway, J.H., Sloane, N.J.A.: Sphere-Packings, Lattices, and Groups. Springer, New York (1987)"},{"key":"461_CR13","doi-asserted-by":"crossref","unstructured":"Danzer, L., Gr\u00fcnbaum, B., Klee, V.: Helly\u2019s theorem and its relatives. In: Convexity, Proceedings of Symposia in Pure Mathematics, vol.\u00a07. American Mathematical Society, Providence, RI (1963)","DOI":"10.1090\/pspum\/007\/0157289"},{"issue":"4","key":"461_CR14","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1145\/88560.88575","volume":"9","author":"DP Dobkin","year":"1990","unstructured":"Dobkin, D.P., Wilks, A.R., Levy, S.V., Thurston, W.P.: Contour tracing by piecewise linear approximations. ACM Trans. Graph. (TOG) 9(4), 389\u2013423 (1990)","journal-title":"ACM Trans. Graph. (TOG)"},{"issue":"3","key":"461_CR15","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1002\/nme.1620310302","volume":"31","author":"DA Field","year":"1991","unstructured":"Field, D.A., Smith, W.D.: Graded tetrahedral finite element meshes. Int. J. Numer. Methods Eng. 31(3), 413\u2013425 (1991)","journal-title":"Int. J. Numer. Methods Eng."},{"key":"461_CR16","volume-title":"Reflection Groups and Coxeter Groups","author":"JE Humphreys","year":"1992","unstructured":"Humphreys, J.E.: Reflection Groups and Coxeter Groups, vol. 29. Cambridge University Press, Cambridge (1992)"},{"key":"461_CR17","doi-asserted-by":"publisher","unstructured":"Iordanov, I., Teillaud, M.: Implementing Delaunay triangulations of the Bolza surface. In: Proceedings of the Thirty-third International Symposium on Computational Geometry, pp. 44:1\u201344:15 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.44. https:\/\/hal.inria.fr\/hal-01568002","DOI":"10.4230\/LIPIcs.SoCG.2017.44"},{"key":"461_CR18","unstructured":"Jamet, P.: Estimations d\u2019erreur pour des \u00e9l\u00e9ments finis droits presque d\u00e9g\u00e9n\u00e9r\u00e9s. Revue fran\u00e7aise d\u2019automatique, informatique, recherche op\u00e9rationnelle. Anal. Num\u00e9rique 10(1), 43\u201360 (1976)"},{"key":"461_CR19","first-page":"241","volume":"123","author":"H Jung","year":"1901","unstructured":"Jung, H.: \u00dcber die kleinste Kugel, die eine r\u00e4umliche Figur einschliesst. J. Reine Angew. Math. 123, 241\u2013257 (1901)","journal-title":"J. Reine Angew. Math."},{"issue":"4","key":"461_CR20","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1137\/1027154","volume":"27","author":"M Klamkin","year":"1985","unstructured":"Klamkin, M.: Inequality for a simplex. SIAM Rev. 27(4), 576 (1985)","journal-title":"SIAM Rev."},{"issue":"2","key":"461_CR21","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0729031","volume":"29","author":"M K\u0159\u00ed\u017eek","year":"1992","unstructured":"K\u0159\u00ed\u017eek, M.: On the maximum angle condition for linear tetrahedral elements. SIAM J. Numer. Anal. 29(2), 513\u2013520 (1992)","journal-title":"SIAM J. Numer. Anal."},{"key":"461_CR22","doi-asserted-by":"crossref","unstructured":"Labelle, F., Shewchuk, J.R.: Isosurface stuffing: fast tetrahedral meshes with good dihedral angles. ACM Trans. Graph. 26(3), 57-1\u201357-10 (2007)","DOI":"10.1145\/1276377.1276448"},{"issue":"19","key":"461_CR23","doi-asserted-by":"publisher","first-page":"5089","DOI":"10.1088\/0305-4470\/25\/19\/020","volume":"25","author":"RV Moody","year":"1992","unstructured":"Moody, R.V., Patera, J.: Voronoi and Delaunay cells of root lattices: classification of their faces and facets by Coxeter-Dynkin diagrams. J. Phys. A Math. Gen. 25(19), 5089 (1992)","journal-title":"J. Phys. A Math. Gen."},{"key":"461_CR24","volume-title":"Elementary differential topology","author":"JR Munkres","year":"1966","unstructured":"Munkres, J.R.: Elementary differential topology, vol. 54. Princeton University Press, Princeton (1966)"},{"issue":"10","key":"461_CR25","doi-asserted-by":"publisher","first-page":"1383","DOI":"10.1002\/(SICI)1097-0207(19990410)44:10<1383::AID-NME616>3.0.CO;2-I","volume":"44","author":"DJ Naylor","year":"1999","unstructured":"Naylor, D.J.: Filling space with tetrahedra. Int. J. Numer. Methods Eng. 44(10), 1383\u20131395 (1999)","journal-title":"Int. J. Numer. Methods Eng."},{"issue":"2","key":"461_CR26","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/BF02574375","volume":"12","author":"V Rajan","year":"1994","unstructured":"Rajan, V.: Optimality of the Delaunay triangulation in $${\\mathbb{R}}^d$$. Discrete Comput. Geom. 12(2), 189\u2013202 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"461_CR27","first-page":"137","volume":"73","author":"J Shewchuk","year":"2002","unstructured":"Shewchuk, J.: What is a good linear finite element? interpolation, conditioning, anisotropy, and quality measures (preprint). Univ. Calif. Berkeley 73, 137 (2002)","journal-title":"Univ. Calif. Berkeley"},{"key":"461_CR28","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1017\/S001309150007783X","volume":"41","author":"D Sommerville","year":"1922","unstructured":"Sommerville, D.: Space-filling tetrahedra in Euclidean space. Proc. Edinb. Math. Soc. 41, 49\u201357 (1922)","journal-title":"Proc. Edinb. Math. Soc."},{"key":"461_CR29","doi-asserted-by":"publisher","DOI":"10.1063\/1.3060143","volume-title":"The Hypercircle in Mathematical Physics","author":"JL Synge","year":"1957","unstructured":"Synge, J.L.: The Hypercircle in Mathematical Physics. CUP Archive, Cambridge (1957)"},{"key":"461_CR30","unstructured":"Theu\u00dfl, T., Moller, T., Groller, M.E.: Optimal regular volume sampling. In: Proceedings of the Visualization, 2001, VIS\u201901, pp. 91\u2013546. IEEE (2001)"},{"key":"461_CR31","unstructured":"Top, J.: Dynkin diagrammen en Wortelsystemen. www.math.rug.nl\/~top\/dynkin.ps"},{"issue":"4","key":"461_CR32","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/S0097-8493(99)00076-X","volume":"23","author":"GM Treece","year":"1999","unstructured":"Treece, G.M., Prager, R.W., Gee, A.H.: Regularised marching tetrahedra: improved iso-surface extraction. Comput. Graph. 23(4), 583\u2013598 (1999)","journal-title":"Comput. Graph."},{"issue":"3","key":"461_CR33","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1137\/0733045","volume":"33","author":"SA Vavasis","year":"1996","unstructured":"Vavasis, S.A.: Stable finite elements for problems with wild coefficients. SIAM J. Numer. Anal. 33(3), 890\u2013916 (1996)","journal-title":"SIAM J. Numer. Anal."},{"key":"461_CR34","doi-asserted-by":"publisher","DOI":"10.1515\/9781400877577","volume-title":"Geometric Integration Theory","author":"H Whitney","year":"1957","unstructured":"Whitney, H.: Geometric Integration Theory. Princeton University Press, Princeton (1957)"}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-020-00461-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-020-00461-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-020-00461-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T00:42:54Z","timestamp":1614818574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-020-00461-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["461"],"URL":"https:\/\/doi.org\/10.1007\/s11786-020-00461-5","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3]]},"assertion":[{"value":"15 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}