## Constrained Construction of Planar Delaunay Triangulations without Flipping

**Authors:**Galishnikova V.V., Pahl P.J.**Issue:**Vol 14, No 2 (2018)**Pages:**154-174**Section:**Articles**URL:**http://journals.rudn.ru/structural-mechanics/article/view/18650**DOI:**http://dx.doi.org/10.22363/1815-5235-2018-14-2-154-174

#### Abstract

### Vera V Galishnikova

Peoples’ Friendship University of Russia (RUDN University)
Email: galishni@gmail.com

6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation Associate Professor, Director of the Department of Architecture and civil engineering, Engineering Academy, RUDN University. Research Interests: Computational Civil Engineering, Building information modeling, Topological computer models of buildings, Computational geometry, Computational mechanics of complex steel structural systems - latticed plates and shells, thin-walled plate and plate-rod structures. Nonlinear finite element analysis of space frames. Nonlinear stability of structures

### Peter Jan Pahl

Technische Universität Berlin
Email: pahl@ifb.bv.tuberlin.de

17 Juni Str., 135, 10623, Berlin, Germany Prof. Dr. Dr. h. c. mult., Department of Civil Engineering, Technical University Berlin (TUB). Research Interests: Mathematical modeling and optimization of comple[ structural systems, Computational Civil Engineering, Building information modeling, Topological computer models of buildings, Computational geometry, Computational mechanics of complex steel structural systems - latticed plates and shells, thin-walled plate and plate-rod structures. Nonlinear finite element analysis of space frames. Nonlinear stability of structures

- Liebling T.M., Pournin L. (2010). Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twins. Documenta Mathematica. Mathematics Subject Classification: 01A65, 4903, 52C99, 68R99, 70-08, 92-08.
- Voronoi G. (1908). Nouvelles applications des paramètres continues à la théorie des forms quadratiques. J. Reine Angew. Math. 134, 198-287.
- Delaunay B.N. (1932). Neue Darstellung der geometrischen Kristallographie. Z. Kristallographie, 84, 109-149.
- Dirichlet G.L. (1850). Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen, J. Reine Angew. Math. 40, 209-227.
- Aurenhammer F. (1987). Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16, 1, 78-96.
- Galishnikova V., Pahl P.J. (2013). Computational Geometry. Lecture Notes.
- Guibas L., Stolfi J. (1985). Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Regions. ACM Trans. on Graphics. V4, No. 2, April 1985.
- Shamos M.I., Hoey D. (1975). Closest-point problems. In Proceedings of the 16th Annual IEEE Symposium on FOCS, 151-162.
- Skvortsov A.V. (2002). Delaunay Triangulation and its applications. Tomsk State University, 128 p. (in Russ.).
- Skvortsov A.V., Mirza N.S. (2006). Algorithms for construction and analysis of triangulation. Tomsk State University Publ., 168 p. (in Russ.).
- Lawson C.L. (1972). Transforming triangulations, Discrete Math. 3, 365-372.
- Joe B. (1991). Construction of three-dimensional Delaunay triangles using local transformations. Comput. Aided Geom. Design 8, 123-142.
- de Loera J.A., Rambau J., Santos F. (2010). Triangulation: structures for triangulations and applications. Algorithms and Computation in Mathematics 25, Springer.
- Edelsbrunner H., Shah N.R. (1996). Incremental topological flipping works regular triangulations. Algorithmica 15, 223-241.
- Baudson C., Klein E. (2006). Berechnung und Visualisierung von Voronoi-Diagrammen in 3D. Diplomarbeit, p. 1-138. Rheinische Friedrich-Wilhelms-Universität Bonn
- Pahl, P.J. (2011). Theory and Application of Polytopes. Lecture notes. Chair of Bauinformatik, Technische Universität Berlin, 107 p.
- Mäntylä, M. (1988). Introduction to Solid Modeling. W.H. Freeman & Co. New York. ISBN: 0-88175-108-1.
- de Berg M., van Krefeld M., Overmars M., Schwarzkopf O. (1997). Computational Geometry: Algorithms and Applications. Chapter 14. Springer. ISBN 3-540-61270-X. 363 p.

#### Views

**Abstract** - 133

**PDF** (English) - 71