Regular triangulations and Steiner points

Zvagel′skiĭ, M.; Proskurnikov, A.; Romanovskiĭ, Yu.

doi:10.1090/S1061-0022-05-00872-1

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