Discrete & Computational Geometry

Maximal (k+1)-crossing-free graphs on a planar point set in convex position, that is, k-triangulations, have received attention in recent literature, motivated by several interpretations of them. We introduce a new way of looking at k-triangulations, namely as complexes of star polygons. With this tool we give new, direct proofs of the fundamental properties of k-triangulations, as well as some new results. This interpretation also opens up new avenues of research that we briefly explore in the last section.

We prove that every finite family of convex sets in the plane satisfying the (4, 3)-property can be pierced by nine points. This improves the bound of 13 proved by Kleitman et al. (Combinatorica 21(2), 221–232 (2001)).

The aim of this paper is to clarify the relationship between Gromov-hyperbolicity and amenability for planar maps.

We consider a geometric optimization problem that arises in network design. Given a set P of n points in the plane, source and destination points s, t∈P, and an integer k>0, one has to locate k Steiner points, such that the length of the longest edge of a bottleneck path between s and t is minimized. In this paper, we present an O(nlog2 n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al. (in Wireless Networks 16, 1033–1043, 2010), who gave an O(n 2logn)-time algorithm. We also study the dual version of the problem, where a value λ>0 is given (instead of k), and the goal is to locate as few Steiner points as possible, so that the length of the longest edge of a bottleneck path between s and t is at most λ. Our algorithms are based on two new geometric structures that we develop—an (α,β)-pair decomposition of P and a floor (1+ε)-spanner of P. For real numbers β>α>0, an (α,β)-pair decomposition of P is a collection $\mathcal{W}=\{(A_{1},B_{1}),\ldots,(A_{m},B_{m})\}$ of pairs of subsets of P, satisfying the following: (i) For each pair $(A_{i},B_{i}) \in\mathcal {W}$ , both minimum enclosing circles of A i and B i have a radius at most α, and (ii) for any p, q∈P, such that |pq|≤β, there exists a single pair $(A_{i},B_{i}) \in\mathcal{W}$ , such that p∈A i and q∈B i , or vice versa. We construct (a compact representation of) an (α,β)-pair decomposition of P in time O((β/α)3 nlogn). In some applications, a simpler (though weaker) grid-based version of an (α,β)-pair decomposition of P is sufficient. We call this version a weak (α,β)-pair decomposition of P. For ε>0, a floor (1+ε)-spanner of P is a (1+ε)-spanner of the complete graph over P with weight function w(p,q)=⌊|pq|⌋. We construct such a spanner with O(n/ε 2) edges in time O((1/ε 2)nlog2 n), even though w is not a metric. Finally, we present two additional applications of an (α,β)-pair decomposition of P. In the first, we construct a strong spanner of the unit disk graph of P, with the additional property that the spanning paths also approximate the number of substantial hops, i.e., hops of length greater than a given threshold. In the second application, we present an O((1/ε 2)nlogn)-time algorithm for computing a one-sided approximation for distance selection (i.e., given k, $1 \le k \le{n \choose2}$ , find the k’th smallest Euclidean distance induced by P), significantly improving the running time of the algorithm of Bespamyatnikh and Segal.

The space of torus translations and degenerations of a projective toric variety forms a toric variety associated to the secondary fan of the integer points in the polytope corresponding to the toric variety. This is used to identify a moduli space of real degenerations with the secondary polytope. A configuration $${{\mathcal {A}}}$$ of real vectors gives an irrational projective toric variety in a simplex. We identify a space of translations and degenerations of the irrational projective toric variety with the secondary polytope of  $${{\mathcal {A}}}$$ . For this, we develop a theory of irrational toric varieties associated to arbitrary fans. When the fan is rational, the irrational toric variety is the nonnegative part of the corresponding classical toric variety. When the fan is the normal fan of a polytope, the irrational toric variety is homeomorphic to that polytope.

Một đa giác nhỏ là một đa giác có đường kính đơn vị. Diện tích tối đa của một đa giác nhỏ với $$n=2m$$ đỉnh chưa được biết đến khi $$m\ge 7$$. Trong bài báo này, chúng tôi xây dựng, cho mỗi $$n=2m$$ và $$m\ge 3$$, một đa giác nhỏ n đỉnh có diện tích là giá trị lớn nhất của một hàm một biến. Chúng tôi cho thấy rằng, cho tất cả các giá trị chẵn $$n\ge 6$$, diện tích đạt được cải thiện hơn $$O(1/n^5)$$ so với đa giác nhỏ n đỉnh tốt nhất được xây dựng trước đó bởi Mossinghoff. Cụ thể, đối với $$n=6$$, đa giác nhỏ 6 đỉnh được xây dựng có diện tích tối đa.