Remote Access St. Petersburg Mathematical Journal

St. Petersburg Mathematical Journal

ISSN 1547-7371(online) ISSN 1061-0022(print)

 
 

 

Regular triangulations and Steiner points


Authors: M. Yu. Zvagel'skii, A. V. Proskurnikov and Yu. R. Romanovskii
Translated by: Yu. R. Romanovskii
Original publication: Algebra i Analiz, tom 16 (2004), nomer 4.
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
Published electronically: June 24, 2005
MathSciNet review: 2090852
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)

  • 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)

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 52B11, 52B35, 68U05


Additional Information

M. Yu. Zvagel'skii
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. Romanovskii
Affiliation: Department of Mathematics and Mechanics, St. Petersburg State University, Universitetskiĭ Prospekt 28, Staryĭ Peterhof, St. Petersburg 198904, Russia
Email: romanov@YR2008.spb.edu

DOI: https://doi.org/10.1090/S1061-0022-05-00872-1
Keywords: Nonconvex polytopes, regular triangulations, Steiner points
Received by editor(s): December 12, 2003
Published electronically: June 24, 2005
Additional Notes: Supported by the CRDF grant RMO-1296-ST-02
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society