Discrete & Computational Geometry

A setP ofn points inR d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn′ interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn′/(d + 1) points. A splitter can be found inO(d 4 +nd 2) time. Using this result, we give anO(nd 4 log1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR 3 we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR 3 for which the number of simplices produced may vary between (n − 1)2 + 1 and 2n − 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.

Recent results obtained by Martini et al. [4] facilitate the proof that there are exactly eight unilateral and equitransitive tilings of the plane by squares of three sizes. This refutes a conjecture by Schattschneider that appears in the book Tilings and Patterns by Grünbaum and Shephard [2].

Chúng tôi chứng minh rằng lõi giới hạn của một ma trận hướng về một mặt phẳng là tinh khiết và có thể thu gọn. Chúng tôi cũng tổng quát hóa định lý phân hoạch trung tâm của Zaslavsky cho các sắp xếp mặt phẳng đến các ma trận hướng về một mặt phẳng.

Discrete exterior calculus (DEC) is a framework for constructing discrete versions of exterior differential calculus objects, and is widely used in computer graphics, computational topology, and discretizations of the Hodge–Laplace operator and other related partial differential equations. However, a rigorous convergence analysis of DEC has always been lacking; as far as we are aware, the only convergence proof of DEC so far appeared is for the scalar Poisson problem in two dimensions, and it is based on reinterpreting the discretization as a finite element method. Moreover, even in two dimensions, there have been some puzzling numerical experiments reported in the literature, apparently suggesting that there is convergence without consistency. In this paper, we develop a general independent framework for analyzing issues such as convergence of DEC without relying on theories of other discretization methods, and demonstrate its usefulness by establishing convergence results for DEC beyond the Poisson problem in two dimensions. Namely, we prove that DEC solutions to the scalar Poisson problem in arbitrary dimensions converge pointwise to the exact solution at least linearly with respect to the mesh size. We illustrate the findings by various numerical experiments, which show that the convergence is in fact of second order when the solution is sufficiently regular. The problems of explaining the second order convergence, and of proving convergence for general p-forms remain open.

We describe a deterministic algorithm for computing the diameter of a finite set of points in R 3 , that is, the maximum distance between any pair of points in the set. The algorithm runs in optimal time O(nlog  n) for a set of n points. The first optimal, but randomized, algorithm for this problem was proposed more than 10 years ago by Clarkson and Shor [11] in their ground-breaking paper on geometric applications of random sampling. Our algorithm is relatively simple except for a procedure by Matoušek [25] for the efficient deterministic construction of epsilon-nets. This work improves previous deterministic algorithms by Ramos [31] and Bespamyatnikh [7], both with running time O(nlog  2 n) . The diameter algorithm appears to be the last one in Clarkson and Shor’s paper that up to now had no deterministic counterpart with a matching running time.

Let $${\mathcal {H}}$$ be a Coxeter hyperplane arrangement in n-dimensional Euclidean space. Assume that the negative of the identity map belongs to the associated Coxeter group W. Furthermore assume that the arrangement is not of type $$A_1^n$$ . Let K be a measurable subset of the Euclidean space with finite volume which is stable by the Coxeter group W and let a be a point such that K contains the convex hull of the orbit of the point a under the group W. In a previous article the authors proved the generalized pizza theorem: that the alternating sum over the chambers T of  $${\mathcal {H}}$$ of the volumes of the intersections $$T\cap (K+a)$$ is zero. In this paper we give a dissection proof of this result. In fact, we lift the identity to an abstract dissection group to obtain a similar identity that replaces the volume by any valuation that is invariant under affine isometries. This includes the cases of all intrinsic volumes. Apart from basic geometry, the main ingredient is a theorem of the authors where we relate the alternating sum of the values of certain valuations over the chambers of a Coxeter arrangement to similar alternating sums for simpler subarrangements called 2-structures introduced by Herb to study discrete series characters of real reduced groups.

We use the Billera-Liu algebra to show how the flag f-vectors of several special classes of polytopes fit into the closed convex hull of the flag f-vectors of all polytopes. In particular, we describe inequalities that define the faces of the closed convex hull of the flag f-vectors of all d-polytopes that are spanned by the flag f-vectors of simplicial, simple, k-simplicial, and k-simple d-polytopes. We also describe inequalities that define the face of the closed convex hull of the flag f-vectors of all d-zonotopes spanned by the flag f-vectors of cubical d-zonotopes, and give an upper bound on the dimension of the span of the flag f-vectors of k-cubical zonotopes. Finally, we strengthen some previously known inequalities for flag f-vectors of zonotopes.

We consider the problem of extending the semistable reduction theorem of [KKMS] from the case of one-parameter families of varieties to families over a base of arbitrary dimension. Following [KKMS], semistable reduction of such families can be reduced to a problem in the combinatorics of polyhedral complexes [AK]. In this paper we solve it in the case when the relative dimension of the morphism is at most three, i.e., for families of surfaces and threefolds.

Green and Sisask showed that the maximal number of 3-term arithmetic progressions in n-element sets of integers is $$\lceil n^2/2\rceil $$ ; it is easy to see that the same holds if the set of integers is replaced by the real line or by any Euclidean space. We study this problem in general metric spaces, where a triple (a, b, c) of points in a metric space is considered a 3-term arithmetic progression if $$d(a,b)=d(b,c)=d(a,c)/2$$ . In particular, we show that the result of Green and Sisask extends to any Cartan–Hadamard manifold (in particular, to the hyperbolic spaces), but does not hold in spherical geometry or in the r-regular tree, for any $$r\ge 3$$ .

Stanley proved that for any centrally symmetric simplicial d-polytope P with $$d\ge 3$$ , $$g_2(P) \ge {d \atopwithdelims ()2}-d$$ . We provide a characterization of centrally symmetric simplicial d-polytopes with $$d\ge 4$$ that satisfy this inequality as equality. This gives a natural generalization of the classical Lower Bound Theorem for simplicial polytopes to the setting of centrally symmetric simplicial polytopes.