P. G. Demidov Yaroslavl State University
International B. N. Delaunay Laboratory
Discrete and Computational Geometry
Second Yaroslavl Summer School
on Discrete and Computational
Geometry
July–August, 2013
Lecture Notes
Yaroslavl 2013
UDC 514
Second Yaroslavl Summer School on Discrete and Computational
Geometry. <...> Funded by Russian Government Grant 220
Contract 11.G34.31.0053
Delaunay Library Series
Head Editors:
N. Dolbilin, H. Edelsbrunner, A. Ivanov
Editors:
V. Buchstaber, V. Dolnikov, R. Karasev, V. Manturov,
N. Moshchevitin, O. Musin, M. Nevskii, I. Sabitov, M. Schtogrin
Cover design by Xixi Edelsbrunner
ISBN 978-5-8397-1006-1
P.G. Demidov
Yaroslavl State University
Contents
Surface Tracking for Physical Simulation and Computer
Graphics
7
Chris Wojtan
Surface Tracking Problem Session
Chris Wojtan
15
Triangulations of two-dimensional surfaces and chromatic
numbers
18
N. Yu. <...> Erokhovets
Stable Length Estimation
Florian Pausinger
29
Introduction to the Geometry of Positive Quadratic Forms
and the Voronoi Reduction Theory
41
N. Dolbilin, A. Garber
Distorted Cubical Complexes and the Covering and Packing with Spheres
50
Herbert Edelsbrunner
Compact storage of cubical complexes for persistent homology computations
58
Hubert Wagner
Analysis of Root Systems
Olga Symonova, Herbert Edelsbrunner
67
Persistent homology (an overview) I
G. Sharygin
71
Persistent homology (an overview) II
G. Sharygin
84
3
Delaunay Library
The International Delaunay Laboratory of Discrete and Computational Geometry introduces a new books series: the Delaunay Library. <...> The Delaunay Laboratory is being funded
by the Russian Government since 2011 and is headed by Herbert
Edelsbrunner. <...> The Delaunay Laboratory entrusts the Editorial Board of the
Delaunay Library – consisting of three Head Editors, N. Dolbilin,
H. Edelsbrunner, and A. Ivanov, and nine Editors, V. Buchstaber,
V. Dolnikov, R. Karasev, V. Manturov, N. Moshchevitin, O. Musin,
M. Nevskii, I. Sabitov, and M. Schtogrin – with the development of
the library. <...> The Delaunay peak, more than four thousand meters high in the Altai mountains of Russia, is as well-known
to alpinists as is the Delaunay triangulation to mathematicians. <...> Among them is the Delaunay Volume <...>
Second_Yaroslavl_Summer_School_on_Discrete_and_Computational_Geometry._July-August,_2013._Lecture_Notes.pdf
P. G.Demidov Yaroslavl State University
International B. N. Delaunay Laboratory
Discrete and Computational Geometry
Second Yaroslavl Summer School
on Discrete and Computational
Geometry
July–August, 2013
Lecture Notes
Yaroslavl 2013
Стр.1
UDC 514
Second Yaroslavl Summer School on Discrete and Computational
Geometry. July–August, 2013. Lecture Notes. — Yaroslavl State
University, 2013. — 94 p.
Funded by Russian Government Grant 220
Contract 11.G34.31.0053
Delaunay Library Series
Head Editors:
N. Dolbilin, H. Edelsbrunner, A. Ivanov
Editors:
V. Buchstaber, V. Dolnikov, R. Karasev, V. Manturov,
N. Moshchevitin, O. Musin, M. Nevskii, I. Sabitov, M. Schtogrin
Cover design by Xixi Edelsbrunner
ISBN 978-5-8397-1006-1
P.G. Demidov
Yaroslavl State University
Стр.2
Contents
Surface Tracking for Physical Simulation and Computer
Graphics
Chris Wojtan
Surface Tracking Problem Session
Chris Wojtan
Triangulations of two-dimensional surfaces and chromatic
numbers
N. Yu. Erokhovets
Stable Length Estimation
Florian Pausinger
29
Introduction to the Geometry of Positive Quadratic Forms
and the Voronoi Reduction Theory
N. Dolbilin, A. Garber
Distorted Cubical Complexes and the Covering and Packing
with Spheres
Herbert Edelsbrunner
Compact storage of cubical complexes for persistent homology
computations
Hubert Wagner
Analysis of Root Systems
Olga Symonova, Herbert Edelsbrunner
Persistent homology (an overview) I
G. Sharygin
Persistent homology (an overview) II
G. Sharygin
84
58
67
71
41
50
15
18
7
3
Стр.3
Delaunay Library
The International Delaunay Laboratory of Discrete and Computational
Geometry introduces a new books series: the Delaunay Library.
Its mission is the advancement of research and education in this field.
Specifically, we propose to publish scientific monographs, collections
of papers on current research, and textbooks whose primary topics
are in the fields of discrete geometry, computational geometry, and
computational topology. The Delaunay Laboratory is being funded
by the Russian Government since 2011 and is headed by Herbert
Edelsbrunner. It constitutes a concerted effort of leading international
specialists to create a new world-class research and educational
center in Discrete and Computational Geometry on the premises of
the P. Demidov Yaroslavl State University. The introduction of the
Delaunay Library is part of its educational and promotional activities.
The Delaunay Laboratory entrusts the Editorial Board of the
Delaunay Library – consisting of three Head Editors, N. Dolbilin,
H. Edelsbrunner, and A. Ivanov, and nine Editors, V. Buchstaber,
V. Dolnikov, R. Karasev, V. Manturov, N. Moshchevitin, O. Musin,
M. Nevskii, I. Sabitov, and M. Schtogrin – with the development of
the library. For a book to be included in this series, it must be approved
by this board. Additional information on the series, including
annotations of the books in preparation, can be found on the web
page of the Laboratory (www.dcglab.uniyar.ac.ru).
Similar to the Laboratory, the series is named in honor of Boris
Delaunay, a brilliant Russian geometer and one of the founders of
modern discrete geometry. He was also a wonderful teacher and famous
mountain climber. The Delaunay peak, more than four thousand
meters high in the Altai mountains of Russia, is as well-known
to alpinists as is the Delaunay triangulation to mathematicians. A
stylized design of the peak created by Xixi Edelsbrunner can be seen
on the front covers of the books in the series, and a hint of the peak’s
contour is given by the letter Λ in the Laboratory logo designed by
A. Akopyan and S. Sharov–Delaunay.
This book is the second in the series. It contains lecture notes of
the Second Yaroslavl Summer School on Discrete and Computational
Geometry that took place in July and August of 2013. We hope this
volume will be useful to all students and post graduates interested in
the state-of-the-art in this field. Currently, several additional volumes
4
Стр.4
are in preparation. Among them is the Delaunay Volume, a collection
of works by Boris Delaunay, selected and commented by his students
N. Dolbilin and M. Schtogrin; the Voronoi Volume, a collection of
papers by Georgii Voronoi, selected and commented by O. Musin;
and a Russian translation of the textbook on Computational Topology
by H. Edelsbrunner and J. L. Harer.
We are confident that the Delaunay Library becomes a valuable
resource for getting acquainted with, studying, teaching, and doing
research in modern discrete and computational geometry and related
topics.
N. Dolbilin, H. Edelsbrunner, and A. Ivanov
5
Стр.5