P. G. Demidov Yaroslavl State University
International B. N. Delaunay Laboratory
Discrete and Computational Geometry
First Yaroslavl Summer School
on Discrete and Computational Geometry
July – August, 2012
Lecture Notes
Yaroslavl 2012
UDC 514
First 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-0945-4
P.G. Demidov
Yaroslavl State University
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 lead 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. <...> We open the series with the First Yaroslavl Summer School on
Discrete and Computational Geometry, which contains lecture notes
accompanying the short courses delivered in July and August of 2012. <...> 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. <...> The list of
courses given at the School is as follows:
• H. Edelsbrunner, Introduction to Computational Geometry and
Topology, 4 lectures, see [1, 2, 3];
• N. Dolbilin, Introduction to the Theory of Periodic Coverings and
Tilings, 2 lectures, see [4, 5, 6];
• O. Musin <...>
First_Yaroslavl_Summer_School_on_Discrete_and_Computational_Geometry._July_August,_2012._Lecture_Notes.pdf
P. G.Demidov Yaroslavl State University
International B. N. Delaunay Laboratory
Discrete and Computational Geometry
First Yaroslavl Summer School
on Discrete and Computational Geometry
July – August, 2012
Lecture Notes
Yaroslavl 2012
Стр.1
UDC 514
First Yaroslavl Summer School on Discrete and Computational
Geometry. July – August, 2012. Lecture Notes. — Yaroslavl State
University, 2012. — 197 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-0945-4
P.G. Demidov
Yaroslavl State University
Стр.2
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 lead 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
3
Стр.3
the peak’s contour is given by the letter Λ in the Laboratory logo
designed by A. Akopyan and S. Sharov–Delaunay.
We open the series with the First Yaroslavl Summer School on
Discrete and Computational Geometry, which contains lecture notes
accompanying the short courses delivered in July and August of 2012.
We hope this volume will be useful to all students and post graduates
interested in the current state-of-the-art in this field. Currently,
several additional volumes 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
4
Стр.4
Table of Contents
N. Dolbilin, H. Edelsbrunner, A. Ivanov, O. Musin
The First Yaroslavl Summer School on Discrete
and Computational Geometry . . . . . . . . . . . 7
В. Д. Володин
Комбинаторика простых многогранников . . . . . . 14
V. L. Dolnikov
On Kneser’s problems . . . . . . . . . . . . . . 51
A. O. Ivanov and A. A. Tuzhilin
Optimal Networks . . . . . . . . . . . . . . . 60
R. Karasev
The Borsuk–Ulam and ham sandwich theorems. . . . . 111
M. Kerber
Robust Geometric Computation . . . . . . . . . . 120
С. В. Матвеев
Компьютерное табулирование трехмерных многообразий 147
Oleg R. Musin
Kissing Problem in three and four dimensions . . . . . 164
5
Стр.5