Document Open Access Logo

Constrained Triangulations, Volumes of Polytopes, and Unit Equations

Authors Michael Kerber, Robert Tichy, Mario Weitzer

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.46.pdf
  • Filesize: 1.14 MB
  • 15 pages

Document Identifiers

Author Details

Michael Kerber
Robert Tichy
Mario Weitzer

Cite AsGet BibTex

Michael Kerber, Robert Tichy, and Mario Weitzer. Constrained Triangulations, Volumes of Polytopes, and Unit Equations. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.46

Abstract

Given a polytope P in R^d and a subset U of its vertices, is there a triangulation of P using d-simplices that all contain U? We answer this question by proving an equivalent and easy-to-check combinatorial criterion for the facets of P. Our proof relates triangulations of P to triangulations of its "shadow", a projection to a lower-dimensional space determined by U. In particular, we obtain a formula relating the volume of P with the volume of its shadow. This leads to an exact formula for the volume of a polytope arising in the theory of unit equations.
Keywords
  • constrained triangulations
  • simplotopes
  • volumes of polytopes
  • projections of polytopes
  • unit equations
  • S-integers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. C. Athanasiadis. Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley. J. Reine Angew. Math., 583:163-174, 2005. Google Scholar
  2. A. Baker and G. Wüstholz. Logarithmic forms and group varieties. J. Reine Angew. Math., 442:19-62, 1993. Google Scholar
  3. F. Barroero, C. Frei, and R. Tichy. Additive unit representations in rings over global fields - a survey. Publ. Math. Debrecen, 79(3-4):291-307, 2011. Google Scholar
  4. M. Beck and R. Sanyal. Combinatorial Reciprocity Theorems. American Mathematical Society, 2016. In preparation, available at URL: http://math.sfsu.edu/beck/crt.html.
  5. W. Bruns and T. Römer. h-vectors of Gorenstein polytopes. J. Combin. Theory Ser. A, 114:65-76, 2007. Google Scholar
  6. H. Croft, K. Falconer, and R. Guy. Unsolved Problems in Geometry. Springer, 1991. Google Scholar
  7. J. de Loera, F. Liu, and R. Yoshida. A generating function for all semi-magic squares and the volume of the Birkhoff polytope. J. Algebraic Combin., pages 113-139, 2009. Google Scholar
  8. J. de Loera, J. Rambau, and F. Santos. Triangulations. Springer, 2010. Google Scholar
  9. T. de Wolff. Polytopes with special simplices. arXiv:1009.6158. Google Scholar
  10. H. Edelsbrunner and M. Kerber. Dual complexes of cubical subdivisions of ℝⁿ. Discrete Comput. Geom., 47(2):393-414, 2012. Google Scholar
  11. I. Emiris and V. Fisikopoulos. Efficient random-walk methods for approximating polytope volume. In Proc. of the 13th Annual Symp. on Comp. Geom., SOCG'14, pages 318:318-318:327, 2014. Google Scholar
  12. G. R. Everest. A "Hardy-Littlewood" approach to the S-unit equation. Compos. Math., 70(2):101-118, 1989. Google Scholar
  13. G. R. Everest. Counting the values taken by sums of S-units. J. Number Theory, 35(3):269-286, 1990. Google Scholar
  14. J. Evertse and H. P. Schlickewei. A quantitative version of the absolute subspace theorem. J. Reine Angew. Math., 548:21-127, 2002. Google Scholar
  15. C. Frei, R. Tichy, and V. Ziegler. On sums of S-integers of bounded norm. Monatsh. Math., 175(2):241-247, 2014. Google Scholar
  16. H. Freudenthal. Simplizialzerlegung beschränkter Flachheit. Ann. of Math., pages 580-582, 1942. Google Scholar
  17. R. Freund. Combinatorial theorems on the simplotope that generalize results on the simplex and cube. Math. Oper. Res., 11(1):169-179, 1986. Google Scholar
  18. I. Gelfand, M. Kapranov, and A. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhäuser, 2008. Google Scholar
  19. K. Győry and K. Yu. Bounds for the solutions of S-unit equations and decomposable form equations. Acta Arith., 123(1):9-41, 2006. Google Scholar
  20. H. Hadwiger. Vorlesungen über Inhalt, Oberfläche und Isoperimetrie. Springer, 1957. Google Scholar
  21. T. Hibi and H. Ohsugi. Special simplices and Gorenstein toric rings. J. Combin. Theory Ser. A, 113:718-725, 2006. Google Scholar
  22. R. Hughes and M. Anderson. Simplexity of the cube. Discrete Math., 158:99-150, 1996. Google Scholar
  23. M. Kerber, R. Tichy, and M. Weitzer. Constrained triangulations, volumes of polytopes, and unit equations. arXiv, 1609.05017, 2016. Google Scholar
  24. J. Matoušek. Lectures in Discrete Geometry. Springer, 2002. Google Scholar
  25. J. Neukirch. Algebraic number theory, volume 322 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, 1999. Google Scholar
  26. K. Nishioka. Algebraic independence by Mahler’s method and S-unit equations. Compositio Math., 92(1):87-110, 1994. Google Scholar
  27. I. Pak. Four questions on Birkhoff polytope. Ann. Comb., 4:83-90, 2000. Google Scholar
  28. V. Reiner and V. Welker. On the Charney-Davis and Neggers-Stanley conjectures. J. Combin. Theory Ser. A, 109(2):247-280, 2005. Google Scholar
  29. F. Santos. A counterexample to the Hirsch conjecture. Ann. of Math., 176:383-412, 2012. Google Scholar
  30. H. P. Schlickewei. S-unit equations over number fields. Invent. Math., 102(1):95-108, 1990. Google Scholar
  31. J. Shewchuk. General-dimensional constrained Delaunay and constrained regular triangulations, I: Combinatorial properties. Discrete Comput. Geom., 39:580-637, 2008. Google Scholar
  32. G. van der Laan and A. Talman. On the computation of fixed points in the product space of unit simplices and an application to noncooperative n person games. Math. Oper. Res., 7(1):1-13, 1982. Google Scholar
  33. G. Ziegler. Lectures on Polytopes. Springer, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact