Skip to main content



On the Complexity of Many Faces in Arrangements of Pseudo-Segments and Circles

We obtain improved bounds on the complexity of many faces in an arrangement of pseudo-segments, circles, or unit circles. The bounds are worst-case optimal for unit circles; they are also worst-case optimal for the case of pseudo-segments except when the number of faces is very small, in which case our upper bound is a polylogarithmic factor away from the best-known lower bound. For general circles, the bounds nearly coincide with the best-known bounds for the number of incidences between points and circles.

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Polyhedral Cones of Magic Cubes and Squares

Using computational algebraic geometry techniques and Hilbert bases of polyhedral cones we derive explicit formulas and generating functions for the number of magic squares and magic cubes.

Maya Ahmed, Jesús De Loera, Raymond Hemmecke

Congruent Dudeney Dissections of Triangles and Convex Quadrilaterals – All Hinge Points Interior to the Sides of the Polygons

Let α and β be polygons with the same area. A Dudeney dissectionofα toβ is a partition of α into parts which can be reassembled to produceβ in the following way. Hinge the parts ofα like a chain along the perimeter of α, then fix one of the parts to formβ with the perimeter of α going into its interior and with its perimeter consisting of the dissection lines in the interior of α, without turning the pieces over. In this paper we discuss a special type of Dudeney dissection of triangles and convex quadrilaterals in which α is congruent toβ and call it acongruent Dudeney dissection. In particular, we consider the case where all hinge points are interior to the sides of the polygonα and β. For this case, we determine all triangles and convex quadrilaterals which have congruent Dudeney dissections.

Jin Akiyama, Gisaku Nakamura

Computing the Hausdorff Distance of Geometric Patterns and Shapes

A very natural distance measure for comparing shapes and patterns is the Hausdorff distance. In this article we develop algorithms for computing the Hausdorff distance in a very general case in which geometric objects are represented by finite collections of k-dimensional simplices in d-dimensional space. The algorithms are polynomial in the size of the input,a ssuming d is a constant. In addition,w e present more efficient algorithms for special cases like sets of points,or line segments,or triangulated surfaces in three dimensions.

Helmut Alt, Peter Braß, Michael Godau, Christian Knauer, Carola Wenk

A Sum of Squares Theorem for Visibility Complexes and Applications

We present a new method to implement in constant amortized time the flip operation of the so-called Greedy Flip Algorithm, an optimal algorithm to compute the visibility complex of a collection of pairwise disjoint bounded convex sets of constant complexity (disks). The method uses simple data structures and only the left-turn predicate for disks; it relies, among other things, on a sum of squares like theorem for visibility complexes stated and proved in this paper. (The sum of squares theorem for a simple arrangement of lines states that the average value of the square of the number of vertices of a face of the arrangement is bounded by a constant.)

Pierre Angelier, Michel Pocchiola

On the Reflexivity of Point Sets

We introduce a new measure for planar point sets S that captures a combinatorial distance that S is from being a convex set: The reflexivityp(S) of S is given by the smallest number of reflex vertices in a simple polygonalization of S. We prove combinatorial bounds on the reflexivity of point sets and study some closely related quantities, including the convex cover number k c (S) of a planar point set, which is the smallest number of convex chains that cover S, and the convex partition number k p (S), which is given by the smallest number of convex chains with pairwise-disjoint convex hulls that cover S.

Esther M. Arkin, Joseph S. B. Mitchell, Sándor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristán, Saurabh Sethia

Geometric Permutations of Large Families of Translates

Let F be a finite family of disjoint translates of a compact convex set K in R2, and let l be an ordered line meeting each of the sets. Then l induces in the obvious way a total order on F. It is known that, up to reversals, at most three different orders can be induced on a given F as l varies. It is also known that the families are of six different types, according to the number of orders and their interrelations. In this paper we study these types closely, focusing on their relations to the given set K, and on what happens as |F| →∞.

Andrei Asinowski, Meir Katchalski, Andreas Holmsen, Helge Tverberg

Integer Points in Rotating Convex Bodies

Let K be a planar convex body symmetric about the origin. We define P(K) as the probability of τ K∩Z2 ≠ {0}, where τ ∈ SO(2) is a random rotation around the origin and SOZ2 denotes the integer lattice, and we let P(v) = inf{P(K) : vol(K) = υ}. By Minkowski’s theorem, P(υ) = 1 for υ > 4, and P(υ) = 0 for υ < π. We describe the behavior of P(υ) in the intervals [π, π + ε0] and [4 - ε0, 4] for a small positive constant ε0.

Imre Bárány, Jiří Matoušek

Complex Matroids Phirotopes and Their Realizations in Rank 2

The motivation for this article comes from the desire to link two seemingly incompatible worlds: oriented matroids and dynamic geometry. Oriented matroids have proven to be a perfect tool for dealing with sidedness information in geometric configurations (for instance for the computation of convex hulls). Dynamic geometry deals with elementary geometric constructions in which moving certain free elements controls the motion of constructively dependent elements In this field the introduction of complex coordinates has turned out to be a “key technology” for achieving a consistent continuous movement of the dependent elements. The additional freedom of an ambient complex space makes it possible to bypass disturbing singularities. Unfortunatly, complex coordinates seem to make it impossible to use oriented matroids which are heavily based on real numbers.

Alexander Below, Vanessa Krummeck, Jürgen Richter-Gebert

Covering the Sphere by Equal Spherical Balls

We show that for any acute ϕ, there exists a covering of Sd by spherical balls of radius ϕ such that no point is covered more than 400d ln d times. It follows that the density is of order at most d ln d, and even at most d ln ln d if the number of balls is polynomial in d. If the number of equal spherical balls is d + 3 then we determine the optimal arrangement.At the end, we described how our and other peoples results yield estimates for the largest origin centred Euclidean ball contained in the convex hull of N points chosen from the sphere.

Károly Böröczky, Gergely Wintsche

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems

In spite of extensive and continuing research, for various geometric search problems (such as nearest neighbor search), the best algorithms known have performance that degrades exponentially in the dimension. This phenomenon is sometimes called the curse of dimensionality. Recent results [37, 38, 40] show that in some sense it is possible to avoid the curse of dimensionality for the approximate nearest neighbor search problem. But must the exact nearest neighbor search problem suffer this curse? We provide some evidence in support of the curse. Specifically we investigate the exact nearest neighbor search problem and the related problem of exact partial match within the asymmetric communication model first used by Miltersen [43] to study data structure problems. We derive non-trivial asymptotic lower bounds for the exact problem that stand in contrast to known algorithms for approximate nearest neighbor search.

Allan Borodin, Rafail Ostrovsky, Yuval Rabani

A Turán-type Extremal Theory of Convex Geometric Graphs

We study Turán-type extremal questions for graphs with an additional cyclic ordering of the vertices, i.e. for convex geometric graphs. If a suitably defined chromatic number of the excluded subgraph is bigger than two then the results on convex geometric graphs resemble very much the classical results from the Tur´an theory. On the other hand, in the bipartite case we show some surprising differences, in particular for trees and forests. For example, the Turán function of some convex geometric forests is of the order Θ(n log n), a growth rate that does not occur in the graph Turán theory. We also obtain still another proof of Füredi’s O(n log n) bound on the number of unit distances in a convex n-gon, together with a lower bound showing the limits of this model. The exact growth of the Turán function for several infinite classes of convex geometric graphs is also determined.

Peter Brass, Gyula Károlyi, Pavel Valtr

On the Inapproximability of Polynomial-programming, the Geometry of Stable Sets, and the Power of Relaxation

The present paper introduces the geometric rank as a measure for the quality of relaxations of certain combinatorial optimization problems in the realm of polyhedral combinatorics. In particular, this notion establishes a tight relation between the maximum stable set problem from combinatorial optimization, polynomial programming from integer non linear programming and norm maximization, a basic problem from convex maximization and computational convexity.

Andreas Brieden, Peter Gritzmann

A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube

We consider the nearest-neighbor problem over the d-cube: given a collection of points in {0, 1}d, find the one nearest to a query point (in the L1 sense). We establish a lower bound of Ω(log log d/ log log log d) on the worst-case query time. This result holds in the cell probe model with (any amount of) polynomial storage and word-size dO(1). The same lower bound holds for the approximate version of the problem, where the answer may be any point further than the nearest neighbor by a factor as large as $$ 2^{\left\lfloor {(\log d)^{1 - \varepsilon } } \right\rfloor } $$ , for any fixed ε > 0.

Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov

Detecting Undersampling in Surface Reconstruction

Current surface reconstruction algorithms perform satisfactorily on well sampled, smooth surfaces without boundaries. However, these algorithms face difficulties with undersampling. Cases of undersampling are prevalent in real data since often these data sample a part of the boundary of an object, or are derived from a surface with high curvature or non-smoothness. In this paper we present an algorithm to detect the boundaries where dense sampling stops and undersampling begins. This information can be used to reconstruct surfaces with boundaries, and also to localize small and sharp features where usually undersampling happens. We report the effectiveness of the algorithm with a number of experimental results. Theoretically, we justify the algorithm with some mild assumptions that are valid for most practical data.

Tamal K. Dey, Joachim Giesen

A Survey of the Hadwiger-Debrunner (p, q)-problem

At the annual meeting of the Swiss Mathematical Society held in September 1956 in Basel, H. Hadwiger presented the following theorem. It was published one year later in a joint paper with H. Debrunner, his colleague at the University of Bern.

Jürgen Eckhoff

Surface Reconstruction by Wrapping Finite Sets in Space

Given a finite point set in ℝ3, the surface reconstruction problem asks for a surface that passes through many but not necessarily all points. We describe an unambiguous definition of such a surface in geometric and topological terms,and sketch a fast algorithm for constructing it. Our solution overcomes past limitations to special point distributions and heuristic design decisions.

Herbert Edelsbrunner

Infeasibility of Systems of Halfspaces

An oriented hyperplane is a hyperplane with designated good and bad sides.The infeasibility of a cell in an arrangement $$\overrightarrow \mathcal{A}$$ of oriented hyperplanes is the number of hyperplanes with this cell on the bad side. With MinInf($$\overrightarrow \mathcal{A}$$) we denote the minimum infeasibility of a cell in the arrangement. A subset of hyperplanes of $$\overrightarrow \mathcal{A}$$ is called an infeasible subsystem if every cell in the induced subarrangement has positive infeasibility. With MaxDis($$\overrightarrow \mathcal{A}$$) we denote the maximal number of disjoint infeasible subsystems of $$\overrightarrow \mathcal{A}$$. For every arrangement $$\overrightarrow \mathcal{A}$$ of oriented hyperplanes $$MinInf(\overrightarrow \mathcal{A} {\text{)}} \geqslant {\text{MaxDis(}}\overrightarrow \mathcal{A} {\text{)}}{\text{.}}$$In this paper we investigate bounds for the ratio of the LHS over the RHS in the above inequality. The main contribution is a detailed discussion of the problem in the case d = 2, i.e., for 2-dimensional arrangements. We prove that $$MinInf(\overrightarrow \mathcal{A} {\text{)}} \leqslant 2\cdot {\text{MaxDis(}}\overrightarrow \mathcal{A} {\text{)}}$$, in this case. An example shows that the factor 2 is best possible. If an arrangement $$\overrightarrow \mathcal{A}$$ of n lines contains a cell of infeasibility n, then the factor can be improved to 3/2, which is again best possible. We also consider the problem for arrangements of pseudolines in the Euclidean plane and show that the factor of 2 suffices in this more general situation.

Stefan Felsner, Nicole Morawe

Combinatorial Generation of Small Point Configurations and Hyperplane Arrangements

A recent progress on the complete enumeration of oriented matroids enables us to generate all combinatorial types of small point configurations and hyperplane arrangements in general dimension, including degenerate ones. This extends a number of former works which concentrated on the non-degenerate case and are usually limited to dimension 2 or 3. Our initial study on the complete list for small cases has shown its potential in resolving geometric conjectures.

Lukas Finschi, Komei Fukuda

Relative Closure and the Complexity of Pfaffian Elimination

We introduce the “relative closure” operation on one-parametric families ofsemi-Pfaffian sets. We show that finite unions of sets obtained with this operation(“limit sets”) constitute a structure,i.e., a Boolean algebra closed under projections. Any Pfaffian expression, i.e., an expression with Boolean operations, quantifiers, equations and inequalities between Pfaffian functions, defines a limit set. The structure of limit sets is effectively o-minimal: there is an upper bound on the complexity of a limit set defined by a Pfaffian expression,in terms of the complexities of the expression and the Pfaffian functions in it.

Andrei Gabrielov

Are Your Polyhedra the Same as My Polyhedra?

“Polyhedron” means different things to different people. There is very little in common between the meaning of the word in topology and in geometry. But even if we confine attention to geometry of the 3-dimensional Euclidean space-as we shall do from now on -“polyhedron” can mean either a solid (as in “Platonic solids”, convex polyhedron, and other contexts), or a surface (such as the polyhedral models constructed from cardboard using “nets”, which were introduced by Albrecht Dürer [[17]] in 1525, or, in a more modern version, by Aleksandrov [[1]]), or the 1-dimensional complex consisting of points (“vertices”) and line-segments (“edges”) organized in a suitable way into polygons (“faces”) subject to certain restrictions (“skeletal polyhedra”, diagrams of which have been presented first by Luca Pacioli [[44]] in 1498 and attributed to Leonardo da Vinci). The last alternative is the least usual one-but it is close to what seems to be the most useful approach to the theory of general polyhedra. Indeed, it does not restrict faces to be planar, and it makes possible to retrieve the other characterizations in circumstances in which they reasonably apply: If the faces of a “surface” polyhedron are simple polygons, in most cases the polyhedron is unambiguously determined by the boundary circuits of the faces. And if the polyhedron itself is without selfintersections, then the “solid” can be found from the faces. These reasons, as well as some others, seem to warrant the choice of our approach.

Branko Grünbaum

Some Algorithms Arising in the Proof of the Kepler Conjecture

By any account, the 1998 proof of the Kepler conjecture is complex. The thesis underlying this article is that the proof is complex because it is highly under-automated. Throughout that proof, manual procedures are used where automated ones would have been better suited. This paper gives a series of nonlinear optimization algorithms and shows how a systematic application of these algorithms would bring substantial simplifications to the original proof.

Thomas C. Hales

The Minimal Number of Triangles Needed to Span a Polygon Embedded in ℝd

Given a closed polygon P having n edges, embedded in ℝd, we give upper and lower bounds for the minimal number of triangles t needed to form a triangulated PL surface embedded in ℝd having P as its geometric boundary. More generally we obtain such bounds for a triangulated (locally flat) PL surface having P as its boundary which is immersed in ℝd and whose interior is disjoint from P. The most interesting case is dimension 3, where the polygon may be knotted. We use the Seifert surface construction to show that for any polygon embedded in ℝ3 there exists an embedded orientable triangulated PL surface having at most 7n2 triangles, whose boundary is a subdivision of P. We complement this with a construction of families of polygons with n vertices for which any such embedded surface requires at least 12n2−O(n) triangles. We also exhibit families of polygons in ℝ3 for which Ω(n2) triangles are required in any immersed PL surface of the above kind. In contrast, in dimension 2 and in dimensions d ≥ 5 there always exists an embedded locally flat PL disk having P as boundary that contains at most n triangles. In dimension 4 there always exists an immersed locally flat PL disk of the above kind that contains at most 3n triangles. An unresolved case is that of embedded PL surfaces in dimension 4, where we establish only an O(n2) upper bound. These results can be viewed as providing qualitative discrete analogues of the isoperimetric inequality for piecewise linear (PL) manifolds. In dimension 3 they imply that the (asymptotic) discrete isoperimetric constant lies between 1/2 and 7.

Joel Hass, Jeffrey C. Lagarias

Jacobi Decomposition and Eigenvalues of Symmetric Matrices

We show that every n-dimensional orthogonal matrix can be factored into O(n2) Jacobi rotations (also called Givens rotations in the literature). It is well known that the Jacobi method,wh ich constructs the eigen-decomposition of a symmetric matrix through a sequence of Jacobi rotations,is slower than the eigenvalue algorithms currently used in practice,but is capable of computing eigenvalues, particularly tiny ones,t o a high relative accuracy. The above decomposition, which to the best of our knowledge is new,s hows that the infinite-precision nondeterministic Jacobi method (in which an oracle is invoked to obtain the correct rotation angle in each Jacobi rotation) can construct the eigen-decomposition with O(n2) Jacobi rotations. The complexity of the nondeterministic Jacobi algorithm motivates the efforts to narrow the gap between the complexity of the known Jacobi algorithms and that of the nondeterministic version. Speeding up the Jacobi algorithm while retaining its excellent numerical properties would be of considerable interest. In that direction,we describe,as an example,a variant of the Jacobi method in which the rotation angle for each Jacobi rotation is computed (in closed-form) through 1-dimensional optimization. We also show that the computation of the closed-form optimal solution of the 1-dimensional problems guarantees convergence of the new method.

W. He, N. Prabhu

Discrete Geometry on Red and Blue Points in the Plane — A Survey —

In this paper, we give a short survey on discrete geometry on red and blue points in the plane, most of whose results were obtained in the past decade. We consider balanced subdivision problems, geometric graph problems, graph embedding problems, Gallai-type problems and others.

Atsushi Kaneko, M. Kano

Configurations with Rational Angles and Trigonometric Diophantine Equations

A subset E of the plane is said to be a configuration with rational angles (CRA) if the angle determined by any three points of E is rational when measured in degrees. We prove that there is a constant C such that whenever a CRA has more than C points, then it can be covered either by a circle and its center or by a pair of points and their bisecting line. The proof is based on the description of all rational solutions of the equation $$ \sin \pi p_1 \cdot \sin \pi p_2 \cdot \sin \pi p_3 \cdot = \sin \pi q_1 \cdot \sin \pi q_2 \cdot \sin \pi q_3 . $$

M. Laczkovich

Reconstructing Sets From Interpoint Distances

Which point sets realize a given distance multiset? Interesting cases include the “turnpike problem” where the points lie on a line, the “beltway problem” where the points lie on a loop, and multidimensional versions. We are interested both in the algorithmic problem of determining such point sets for a given collection of distances and the combinatorial problem of finding bounds on the maximum number of different solutions. These problems have applications in genetics and crystallography.We give an extensive survey and bibliography in an effort to connect the independent efforts of previous researchers, and present many new results. In particular, we give improved combinatorial bounds for the turnpike and beltway problems. We present a pseudo-polynomial time algorithm as well as a practical O(2nn log n)-time algorithm that find all solutions to the turnpike problem, ann show that certain other variants of the problem are NP-hard. We conclude with a list of open problems.

Paul Lemke, Steven S. Skiena, Warren D. Smith

Dense Packings of Congruent Circles in Rectangles with a Variable Aspect Ratio

We use computational experiments to find the rectangles of minimum area into which a given number n of non-overlapping congruent circles can be packed. No assumption is made on the shape of the rectangles. Most of the packings found have the usual regular square or hexagonal pattern. However, for 1495 values of n in the tested range n≤ 5000, specifically, for n = 49, 61, 79, 97, 107, …4999, we prove that the optimum cannot possibly be achieved by such regular arrangements.The evidence suggests that the limiting height-to-width ratio of rectangles containing an optimal hexagonal packing of circles tends to $$ 2 - \sqrt 3 $$ as n → ∞, if the limit exists.

Boris D. Lubachevsky, Ronald Graham

Colorings and Homomorphisms of Minor Closed Classes

We relate acyclic (and star) chromatic number of a graph to the chromatic number of its minors and as a consequence we show that the set of all triangle free planar graphs is homomorphism bounded by a triangle free graph. This solves a problem posed in [[15]]. It also improves the best known bound for the star chromatic number of planar graphs from 80 to 30. Our method generalizes to all minor closed classes and puts Hadwiger conjecture in yet another context.

Jaroslav Nešetřil, Patrice Ossona de Mendez

Conflict-free Colorings

A coloring of the elements of a planar point set P is said to be conflict-free if, for every closed disk D whose intersection with P is nonempty, there is a color that occurs in D ∩ P precisely once. We solve a problem of Even, Lotker, Ron, and Smorodinsky by showing that any conflict-free coloring of every set of n points in the plane uses at least c log n colors, for an absolute constant c > 0.Moreover, the same assertion is true for homothetic copies of any convex body D, in place of a disk.

János Pach, Géza Tóth

New Complexity Bounds for Cylindrical Decompositions of Sub-Pfaffian Sets

Tarski-Seidenberg principle plays a key role in real algebraic geometry and its applications. It is also constructive and some efficient quantifier elimination algorithms appeared recently. However, the principle is wrong for first-order theories involving certain real analytic functions (e.g., an exponential function). In this case a weaker statement is sometimes true, a possibility to eliminate onesort ofq uantifiers (either ∀ or ∃). We construct an algorithm for a cylindrical cell decomposition ofa closed cube In ⊂ Rn compatible with a semianalytic subset S ⊂ In, defined by analytic functions from a certain broad finitely defined class (Pfaffian functions), modulo an oracle for deciding emptiness of such sets. In particular the algorithm is able to eliminate one sort ofq uantifiers from a first-order formula. The complexity of the algorithm and the bounds on the output are doubly exponential in O(n2).

Savvas Pericleous, Nicolai Vorobjov

Note on the Chromatic Number of the Space

The chromatic number of the space is the minimum number of colors needed to color the points of the space so that every two points unit distance apart have different colors. We show that this number is at most 15, improving the best known previous bound of 18.References

Radoš Radoičić, Géza Tóth

Expansive Motions and the Polytope of Pointed Pseudo-Triangulations

We introduce the polytope of pointed pseudo-triangulations of a point set in the plane, defined as the polytope of infinitesimal expansive motions of the points subject to certain constraints on the increase of their distances. Its 1-skeleton is the graph whose vertices are the pointed pseudo-triangulations of the point set and whose edges are flips of interior pseudo-triangulation edges.

Günter Rote, Francisco Santos, Ileana Streinu

Some Recent Quantitative and Algorithmic Results in Real Algebraic Geometry

This paper offers a short survey of two topics. In the first section we describea new bound on the Betti numbers of semi-algebraic sets whose proof rely onthe Thom-Milnor bound for algebraic sets and the Mayer-Vietoris long exactsequence. The second section describes the best complexity results and practicalimplementations currently available for finding real solutions of systems ofpolynomial equations and inequalities. In both sections, the consideration ofcritical points will play a key role.

Marie-Françoise Roy

A Discrete Isoperimetric Inequality and Its Application to Sphere Packings

We consider finite packings of equal spheres in Euclidean 3–space E3. The convex hull of the sphere centers is the packing polytope. In the first part of the paper we prove a tight inequality between the surface area of the packing polytope and the number of sphere centers on its boundary, and investigate in particular the equality cases. The inequality follows from a more general inequality for cell complexes on packing polytopes.

Peter Scholl, Achill Schürmann, Jörg M. Wills

On the Number of Maximal Regular Simplices Determined by n Points in Rd

A set V = {x1,…, x n } of n distinct points in Euclidean d-space ℝd determines 2n distances ∥x j − x i ∥ (1 ≤ i < j ≤ n). Some of these distances may be equal. Many questions concerning the distribution of these distances have been asked (and, at least partially, answered). E.g., what is the smallest possible number of distinct distances, as a function of d and n? How often can a particular distance (say, one) occur and, in particular, how often can the largest (resp., the smallest) distance occur?

Zvi Schur, Micha A. Perles, Horst Martini, Yaakov S. Kupitz

Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem

A recent result by Pach and Pinchasi on so-called balanced lines of a finite two-colored point set in the plane is related to other facts on halving triangles in 3-space and to a special case of the Generalized Lower Bound Theorem for convexpo lytopes.

Micha Sharir, Emo Welzl

Quantizing Using Lattice Intersections

The usual quantizer based on an n-dimensional lattice Λ maps a point x ∈ ℝnto a closest lattice point. Suppose Λ is the intersection of lattices Λ1,…,Λ r . Then one may instead combine the information obtained by simultaneously quantizing x with respect to each of the Λ i . This corresponds to decomposing ℝn into a honeycomb of cells which are the intersections of the Voronoi cells for the Λi, and identifying the cell to which x belongs. This paper shows how to write several standard lattices (the face-centered and body-centered cubic lattices, the root lattices D4, E6*E8, the Coxeter-Todd, Barnes-Wall and Leech lattices, etc.) in a canonical way as intersections of a small number of simpler, decomposable, lattices. The cells of the honeycombs are given explicitly and the mean squared quantizing error calculated in the cases when the intersection lattice is the face-centered or body-centered cubic lattice or the lattice D4.

N. J. A. Sloane, B. Beferull-Lozano

Note on a Generalization of Roth’s Theorem

We give a simple proof that for sufficiently large N, every subset of of size[N2]of size at least δN2 contains three points of the form (a,b), (a + d, b), (a, b + d).

József Solymosi

Arrangements, Equivariant Maps and Partitions of Measures by k-Fans

We study topological and combinatorial structures that arise in the problem of finding α-partitions of m spherical measures by k-fans. An elegant construction of I. Bárány and J. Matoušek, [[3]], [[4]], shows that this problem can be reduced to the question whether there exists a G-equivariant map f: V2(ℝ3) → VP \ ∩AP where G is a subgroup of a dihedral group $$ \mathbb{D}_{2n} $$ while the target space VP\∩AP is the complement of a G-invariant, linear subspace arrangement AP. We demonstrate that in many cases the relevant topological obstructions for the existence of these equivariant maps can be computed by a variety of geometric, combinatorial and algebraic ideas.

Siniša T. Vrećica, Rade T. Živaljević

Qualitative Infinite Version of Erdős’ Problem About Empty Polygons

The well-known problem of Erdős-Szekeres in Discrete Geometry is about realizations of convex polygons P with a given number of vertices in a finite set F ⊂ ℝ2, which means that V (P), the vertex set of P, is a subset of F [[5]],[[6]]. See the very good survey [[11]].

Tudor Zamfirescu
Weitere Informationen