Skip to main content

Über dieses Buch

The present volume is a collection of a dozen survey articles, dedicated to the memory of the famous Hungarian geometer, László Fejes Tóth, on the 99th anniversary of his birth. Each article reviews recent progress in an important field in intuitive, discrete, and convex geometry. The mathematical work and perspectives of all editors and most contributors of this volume were deeply influenced by László Fejes Tóth.



Atoms for Parallelohedra

A parallelohedron is a convex polyhedron which tiles 3-dimensional space by translations only. A polyhedron σ is said to be an atom for the set Π of parallelohedra if for each parallelohedron P in Π, there exists an affine-stretching transformation A: ℝ3 → ℝ3 such that A(P) is the union of a finite number of copies of σ. In this paper, we will present two different atoms for the parallelohedra, and determine the number of these atoms used to make up each parallelohedron. We will also show an arrangement of the parallelohedra in lattice-like order and introduce the notion of indecomposability.
Jin Akiyama, Midori Kobayashi, Hiroshi Nakagawa, Gisaku Nakamura, Ikuro Sato

Tarski’s Plank Problem Revisited

In the 1930’s, Tarski introduced his plank problem at a time when the field Discrete Geometry was about to born. It is quite remarkable that Tarski’s question and its variants continue to generate interest in the geometric and analytic aspects of coverings by planks in the present time as well. The paper is of a survey type with some new results and with a list of open research problems on the discrete geometric side of the plank problem.
Károly Bezdek

Dense Packing of Space with Various Convex Solids

One of the basic problems in discrete geometry is to determine the most efficient packing of congruent replicas of a given convex set K in the plane or in space. The most commonly used measure of efficiency is density. Several types of the problem arise depending on the type of isometries allowed for the packing: packing by translates, lattice packing, translates and point reflections, or all isometries. Due to its connections with number theory, crystallography, etc., lattice packing has been studied most extensively. In two dimensions the theory is fairly well developed, and there are several significant results on lattice packing in three dimensions as well. This article surveys the known results, focusing on the most recent progress. Also, many new problems are stated, indicating directions in which future development of the general packing theory in three dimensions seems feasible.
András Bezdek, Włodzimierz Kuperberg

Geometric Problems on Coverage in Sensor Networks

In this article we survey results and state some open problems that are motivated by sensor networks applications.
Peter Brass

Applications of an Idea of Voronoĭ, a Report

The idea of Voronoĭ’s proof of his well-known criterion that a positive definite quadratic form is extreme if and only if it is eutactic and perfect, is as follows: Identify positive definite quadratic forms on 𝔼 d with their coefficient vectors in \({\mathbb{E}^{\frac{1}{d}\left( {d + 1} \right)}}\). This translates certain problems on quadratic forms into more transparent geometric problems in \({\mathbb{E}^{\frac{1}{d}\left( {d + 1} \right)}}\) which, sometimes, are easier to solve. Since the 1960s this idea has been applied successfully to various problems of quadratic forms, lattice packing and covering of balls, the Epstein zeta function, closed geodesics on the Riemannian manifolds of a Teichmüller space, and other problems.
This report deals with recent applications of Voronoĭ’s idea. It begins with geometric properties of the convex cone of positive definite quadratic forms and a finiteness theorem. Then we describe applications to lattice packings of balls and smooth convex bodies, to the Epstein zeta function and a generalization of it and, finally, to John type and minimum position problems.
Peter M. Gruber

Uniform Polyhedrals

Half a century ago H. S. M. Coxeter, M. S. Longuet-Higgins and J. C. P. Miller published a very influential paper on “Uniform Polyhedra” [7]. These are finite polyhedra with regular polygons as faces, and with vertices in a single orbit under symmetries. Uniform polyhedrals are defined by the same conditions, but with finite replaced by locally finite, and the additional explicit requirement that there are no coinciding elements (vertices, edges or faces); this was self-understood in [7]. Coplanar faces, collinear edges, and partial overlaps are allowed for uniform polyhedrals, as they are for uniform polyhedra. It is somewhat surprising that no systematic study of infinite uniform polyhedrals has been undertaken so far. There are three distinct classes of such polyhedrals — rods, slabs, and sponges. The beginnings of their investigation form the core of this article, and many open problems become evident. Illustrations serve to shorten the explanations, but also to highlight the difficulty of presenting polyhedrals graphically. Applications of such polyhedrals and their relatives in fields such as architecture, biology, engineering, and others are discussed as well, as are the shortcomings of the mathematical reviewing journals in reporting these and related applications of geometry.
Branko Grünbaum

Geometric Transversal Theory: T(3)-Families in the Plane

A line that intersects every member of a finite family F of convex sets in the plane is called a line transversal to F. In this paper we will survey the main results and open problems concerning T(3)-families: Finite families of convex sets in the plane in which every subfamily of size 3 admit a line transversal.
Andreas F. Holmsen

Transversals, Topology and Colorful Geometric Results

Suppose we have two convex sets A and B in euclidean d-space ℝ d . Assume the only information we have about A and B comes from the space of their transversal lines. Can we determine whether A and B have a point in common? For example, suppose the space of their transversal lines has an essential curve; that is, suppose there is a line that moves continuously in ℝ d , always remaining transversal to A and B, and comes back to itself with the opposite orientation. If this is so, then A must intersect B, otherwise there would be a hyperplane H separating A from B; but it turns out that our moving line becomes parallel to H at some point on its trip, which is a contradiction to the fact that the moving line remains transversal to the two sets. If we have three convex sets A, B and C, for example, in ℝ3, then our essential curve does not give us sufficient topological information. In this case, to detect whether ABC ≠ ϕ, we need a 2-dimensional cycle. So, for example, if we can continuously choose a transversal line parallel to every direction, then there must be a point in ABC, otherwise if not, the same is true for π(A)∩π(B)∩π(C), for a suitable orthogonal projection π: ℝ3H where H is a plane through the origin (see [4, Lemma 3.1]). Hence clearly there is no transversal line orthogonal to H.
L. Montejano

Survey on Decomposition of Multiple Coverings

The study of multiple coverings was initiated by Davenport and L. Fejes Tóth more than 50 years ago. In 1980 and 1986, the first named author published the first papers about decomposability of multiple coverings. It was discovered much later that, besides its theoretical interest, this area has practical applications to sensor networks. Now there is a lot of activity in this field with several breakthrough results, although, many basic questions are still unsolved. In this survey, we outline the most important results, methods, and questions.
János Pach, Dömötör Pálvölgyi, Géza Tóth

Hanani-Tutte and Related Results

We investigate under what conditions crossings of adjacent edges and pairs of edges crossing an even number of times are unnecessary when drawing graphs. This leads us to explore the Hanani-Tutte theorem and its close relatives, emphasizing the intuitive geometric content of these results.
Marcus Schaefer

Extremal Properties of Random Mosaics

László Fejes Tóth’s fascinating book [2] demonstrates in many ways the phenomenon that figures of discrete or convex geometry that are very economical, namely solving an extremal problem of isoperimetric type, often show a high degree of symmetry. Among the examples are also planar mosaics where, for instance, an extremal property leads to the hexagonal pattern. Mosaics, or tessellations, have become increasingly important for applications. Random tessellations in two or three dimensions have been suggested as models for various real structures. We refer, e.g., to chapter 10 of the book by Stoyan, Kendall, Mecke [35] and to the book by Okabe, Boots, Sugihara, and Chiu [29] on Voronoi tessellations, which also contains a chapter on random mosaics. Apart from possible applications, random mosaics are also an interesting object of study from a purely geometric point of view. Among the results of geometric appeal that have been obtained, some concern extremal problems for (roughly speaking) expected sizes of average cells under some side condition, leading to random mosaics with high symmetry or of a very simple type, namely made up of parallelepipeds only. High symmetry here means that the distribution of the random mosaic, which is usually assumed to be translation invariant, is also invariant under rotations. Extremal problems for the sizes of average cells (not taking expectations) seem senseless at first, since extrema cannot be attained.
Rolf Schneider

Conflict-Free Coloring and its Applications

Let H = (V, E) be a hypergraph. A conflict-free coloring of H is an assignment of colors to V such that, in each hyperedge eE, there is at least one uniquely-colored vertex. This notion is an extension of the classical graph coloring. Such colorings arise in the context of frequency assignment to cellular antennae, in battery consumption aspects of sensor networks, in RFID protocols, and several other fields. Conflict-free coloring has been the focus of many recent research papers. In this paper, we survey this notion and its combinatorial and algorithmic aspects.
Shakhar Smorodinsky
Weitere Informationen

Premium Partner