St. Petersburg Mathematical Society

Author(s): M. Yu. Zvagel'skii; A. V. Proskurnikov; Yu. R. Romanovskii
Translated by: Yu. R. Romanovskii
Original publication: Algebra i Analiz, tom 16 (2004), vypusk 4.
Journal: St. Petersburg Math. J. 16 (2005), 673-690.
MSC (2000): Primary 52B11; Secondary 52B35, 68U05
Posted: June 24, 2005
Retrieve article in: PDF DVI PostScript

Abstract: Gel'fand, Zelevinskii, 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.

1.: I. M. Gel'fand, A. V. Zelevinskii, and M. M. Kapranov, Discriminants of polynomials in several variables and triangulations of Newton polyhedra, Algebra i Analiz 2 (1990), no. 3, 1-62; English transl., Leningrad Math. J. 2 (1991), no. 3, 449-505. MR 1073208 (91m:14080)
2.: L. J. Billera, P. Filliman, and B. Sturmfels, Constructions and complexity of secondary polytopes, Adv. Math. 83 (1990), 155-179. MR 1074022 (92d:52028)
3.: A. V. Proskurnikov and Yu. R. Romanovskii, On regular triangulations of nonconvex polyhedra, Uspekhi Mat. Nauk 57 (2002), no. 4, 185-186; English transl., Russian Math. Surveys 57 (2002), no. 4, 817-818. MR 1942526
4.: J. Ruppert and R. Seidel, On the difficulty of triangulating three-dimensional nonconvex polyhedra, Discrete Comput. Geom. 7 (1992), 227-253. MR 1149654 (93g:68144)
5.: 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.
6.: -, Updating and constructing constrained Delaunay and constrained regular triangulations by flips, Proceedings of the 19th Annual Symposium on Computational Geometry, 2003, pp. 181-190.
7.: 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.
8.: H. Edelsbrunner and N. R. Shah, Incremental topological flipping works for regular triangulations, Algorithmica 15 (1996), 223-241. MR 1368251 (96j:65161)
9.: Siu-Wing Cheng, T. K. Dey, H. Edelsbrunner, M. A. Facello, and Shang-Hua Teng, Sliver exudation, J. ACM 47 (2000), 883-904. MR 1865932 (2002j:68097)
10.: F. Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM J. Comput. 16 (1987), no. 1, 78-96. MR 0873251 (88d:68096)
11.: G. M. Ziegler, Lectures on polytopes, Grad. Texts in Math., vol. 152, Springer-Verlag, New York, 1995. MR 1311028 (96a:52011)
12.: L. G. Khachiyan, A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR 244 (1979), no. 5, 1093-1096; English transl., Soviet Math. Dokl. 20 (1979), no. 1, 191-194. MR 0522052 (80g:90071)
13.: F. P. Preparata and M. I. Shamos, Computational geometry. An introduction, Springer-Verlag, New York, 1985. MR 0805539 (87d:68102)
14.: E. Schönhardt, Über die Zerlegung von Dreieckspolyedern in Tetraeder, Math. Ann. 98 (1928), 309-312.
15.: J. Rambau, On a generalization of Schönhardt's polyhedron, MSRI Preprint no. 2003-13, 2003.
16.: B. Huber, J. Rambau, and F. Santos, The Caley trick, lifting subdivisions, and the Bohne-Dress theorem on zonotopal tilings, J. Eur. Math. Soc. (JEMS) 2 (2000), 179-198. MR 1763304 (2001i:52017)

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 52B11, 52B35, 68U05

M. Yu. Zvagel'skii
Affiliation: Department of Mathematics and Mechanics, St. Petersburg State University, Universitetskii Prospekt 28, Staryi Peterhof, St. Petersburg 198904, Russia
Email: zvag@pdmi.ras.ru

A. V. Proskurnikov
Affiliation: Department of Mathematics and Mechanics, St. Petersburg State University, Universitetskii Prospekt 28, Staryi Peterhof, St. Petersburg 198904, Russia
Email: anton@AP9560.spb.edu

Yu. R. Romanovskii
Affiliation: Department of Mathematics and Mechanics, St. Petersburg State University, Universitetskii Prospekt 28, Staryi Peterhof, St. Petersburg 198904, Russia
Email: romanov@YR2008.spb.edu

DOI: 10.1090/S1061-0022-05-00872-1
PII: S 1061-0022(05)00872-1
Keywords: Nonconvex polytopes, regular triangulations, Steiner points
Received by editor(s): 12/DEC/2003
Posted: June 24, 2005
Additional Notes: Supported by the CRDF grant RMO-1296-ST-02
Copyright of article: Copyright 2005, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN: 1547-7371(e) ISSN: 1061-0022(p)

Previous issue \| Table of contents \| Next issue Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS