Regular triangulations and Steiner points
HTML articles powered by AMS MathViewer
- by
M. Yu. Zvagel′skiĭ, A. V. Proskurnikov and Yu. R. Romanovskiĭ
Translated by: Yu. R. Romanovskiĭ - St. Petersburg Math. J. 16 (2005), 673-690
- DOI: https://doi.org/10.1090/S1061-0022-05-00872-1
- Published electronically: June 24, 2005
- PDF | Request permission
Abstract:
Gel′fand, Zelevinskiĭ, and Kapranov showed that the regular triangulations of a “primary” convex polytope can be viewed as the vertices of another convex polytope, which is said to be secondary. Billera, Filliman, and Sturmfels gave a geometric construction of the secondary polytope, based upon Gale transforms. We apply this construction to describing regular triangulations of nonconvex polytopes. We also discuss the problem of triangulating nonconvex polytopes with Steiner points.References
- I. M. Gel′fand, A. V. Zelevinskiĭ, and M. M. Kapranov, Discriminants of polynomials in several variables and triangulations of Newton polyhedra, Algebra i Analiz 2 (1990), no. 3, 1–62 (Russian); English transl., Leningrad Math. J. 2 (1991), no. 3, 449–505. MR 1073208
- Louis J. Billera, Paul Filliman, and Bernd Sturmfels, Constructions and complexity of secondary polytopes, Adv. Math. 83 (1990), no. 2, 155–179. MR 1074022, DOI 10.1016/0001-8708(90)90077-Z
- A. V. Proskurnikov and Yu. R. Romanovskiĭ, On regular triangulations of nonconvex polyhedra, Uspekhi Mat. Nauk 57 (2002), no. 4(346), 185–186 (Russian); English transl., Russian Math. Surveys 57 (2002), no. 4, 817–818. MR 1942526, DOI 10.1070/RM2002v057n04ABEH000546
- Jim Ruppert and Raimund Seidel, On the difficulty of triangulating three-dimensional nonconvex polyhedra, Discrete Comput. Geom. 7 (1992), no. 3, 227–253. MR 1149654, DOI 10.1007/BF02187840
- J. R. Shewchuk, A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations, Proceedings of the 14th Annual Symposium on Computational Geometry, 1998, pp. 76–85.
- —, Updating and constructing constrained Delaunay and constrained regular triangulations by flips, Proceedings of the 19th Annual Symposium on Computational Geometry, 2003, pp. 181–190.
- B. N. Delaunay, Sur la sphère vide, Izv. Akad. Nauk SSSR Ser. 7 Otdel. Mat. i Estestv. Nauk (Bull. Acad. Sci. URSS Ser. 7 Cl. Sci. Math. Naturelles) 1934, no. 6, 793–800.
- H. Edelsbrunner and N. R. Shah, Incremental topological flipping works for regular triangulations, Algorithmica 15 (1996), no. 3, 223–241. MR 1368251, DOI 10.1007/s004539900013
- Siu-Wing Cheng, Tamal K. Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng, Sliver exudation, J. ACM 47 (2000), no. 5, 883–904. MR 1865932, DOI 10.1145/355483.355487
- F. Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM J. Comput. 16 (1987), no. 1, 78–96. MR 873251, DOI 10.1137/0216006
- Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1
- L. G. Hačijan, A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR 244 (1979), no. 5, 1093–1096 (Russian). MR 522052
- Franco P. Preparata and Michael Ian Shamos, Computational geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR 805539, DOI 10.1007/978-1-4612-1098-6
- E. Schönhardt, Über die Zerlegung von Dreieckspolyedern in Tetraeder, Math. Ann. 98 (1928), 309–312.
- J. Rambau, On a generalization of Schönhardt’s polyhedron, MSRI Preprint no. 2003–13, 2003.
- Birkett Huber, Jörg Rambau, and Francisco Santos, The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings, J. Eur. Math. Soc. (JEMS) 2 (2000), no. 2, 179–198. MR 1763304, DOI 10.1007/s100970050003
Bibliographic Information
- M. Yu. Zvagel′skiĭ
- Affiliation: Department of Mathematics and Mechanics, St. Petersburg State University, Universitetskiĭ Prospekt 28, Staryĭ Peterhof, St. Petersburg 198904, Russia
- Email: zvag@pdmi.ras.ru
- A. V. Proskurnikov
- Affiliation: Department of Mathematics and Mechanics, St. Petersburg State University, Universitetskiĭ Prospekt 28, Staryĭ Peterhof, St. Petersburg 198904, Russia
- Email: anton@AP9560.spb.edu
- Yu. R. Romanovskiĭ
- Affiliation: Department of Mathematics and Mechanics, St. Petersburg State University, Universitetskiĭ Prospekt 28, Staryĭ Peterhof, St. Petersburg 198904, Russia
- Email: romanov@YR2008.spb.edu
- Received by editor(s): December 12, 2003
- Published electronically: June 24, 2005
- Additional Notes: Supported by the CRDF grant RMO-1296-ST-02
- © Copyright 2005 American Mathematical Society
- Journal: St. Petersburg Math. J. 16 (2005), 673-690
- MSC (2000): Primary 52B11; Secondary 52B35, 68U05
- DOI: https://doi.org/10.1090/S1061-0022-05-00872-1
- MathSciNet review: 2090852