The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of the complete graph $K_n$ is \(H(n) := \frac 1 4 łfloor\fracn2\rfloor łfloor\fracn-12\rfloor łfloor\fracn-22\rfloor łfloor\fracn-32\rfloor.\) Ábrego et al. [ Discrete Comput. Geom., 52 (2014), pp. 743--753] introduced the notion of shellability of a drawing $D$ of $K_n$. They proved that if $D$ is $s$-shellable for some $s\geq\lfloor\frac{n}{2}\rfloor$, then $D$ has at least $H(n)$ crossings. This is the first combinatorial condition on a drawing that guarantees at least $H(n)$ crossings. In this work, we generalize the concept of $s$-shellability to bishellability, where the former implies the latter in the sense that every $s$-shellable drawing is, for any $b \leq s-2$, also $b$-bishellable. Our main result is that $(\lfloor \frac{n}{2} \rfloor-2)$-bishellability of a drawing $D$ of $K_n$ also guarantees, with a simpler proof than for $s$-shellability, that $D$ has at least $H(n)$ crossings. We exhibit a drawing of $K_{11}$ that has $H(11)$ crossings, is 3-bishellable, and is not $s$-shellable for any $s\geq5$. This shows that we have properly extended the class of drawings for which the Harary--Hill conjecture is proved. Moreover, we provide an infinite family of drawings of $K_n$ that are $(\lfloor \frac{n}{2} \rfloor-2)$-bishellable, but not $s$-shellable for any $s\geq\lfloor\frac{n}{2}\rfloor$.

Given a set B of n black points in general position, we say that a set of white points W blocks B if in the Delaunay triangulation of B ∪ W there is no edge connecting two black points. We give the following bounds for the size of the smallest set W blocking B : (i) 3 n / 2 white points are always sufficient to block a set of n black points, (ii) if B is in convex position, 5 n / 4 white points are always sufficient to block it, and (iii) at least n − 1 white points are always necessary to block a set of n black points.

Around 1958, Hill conjectured that the crossing number CRg(Kn) of the complete graph KKn is Z(n):=1/4 ⌊ n/2 ⌋ ⌊(n-1)/2⌋ ⌊ (n-2)/2 ⌋ ⌊ (n-3)/2 ⌋ and provided drawings of Kn with exactly Z(n) crossings. Towards the end of the century, substantially different drawings of Kn with Z(n) crossings were found. These drawings are 2-page book drawings, that is, drawings where all the vertices are on a line l (the spine) and each edge is fully contained in one of the two half-planes (pages) defined by l. The 2-page crossing number of Kn, denoted by ν2(Kn), is the minimum number of crossings determined by a 2-page book drawing of Kn. Since CRG(Kn) ≤ ν2(Kn) and ν2(Kn) ≤ Z(n), a natural step towards Hill's Conjecture is the weaker conjecture ν2(Kn) = Z(n), that was popularized by Vrt'o. In this paper we develop a novel and innovative technique to investigate crossings in drawings of Kn, and use it to prove that ν2(Kn) = Z(n). To this end, we extend the inherent geometric definition of k-edges for finite sets of points in the plane to topological drawings of Kn. We also introduce the concept of ≤≤k-edges as a useful generalization of ≤k-edges. Finally, we extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of Kn in terms of its number of k-edges to the topological setting.

We prove that for every centrally symmetric convex polygon Q, there exists a constant α such that any αk-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Tóth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.

In this paper we propose a discrete local optimization method in order to solve the problem of computing the thinnest annulus containing a set of points S c IEd for d = 2 and d = 3.Despite the extreme simplicity and worst case O(nd+l) complexity of the algorithm, we give empirical evidence that the algorithm performs very well (close to linear time) if the input is almost round.We also present some theoretical results that give a partial explanation of this behavior: although the number of local minima may be quadratic (already for d = 2), almost round configurations of points having more than one local minimum are quite degenerate.and thus very unlikely to be encountered in practice.Finally, we show that for d = 2 the problem can be solved in O(n) expected time for a fairly general family of almost round sets. IntroductionThe problem of computing the thinnest annulus containing a given set of points 5' c E2, the so called roundness problem, has been extensively studied.The main motivation for this problem comes from tolerancing metrology: given an object that has to be tested for circularity, take a sample of points from the object and *Partially supported by DGES grant PB96-0005-COZ-01.

Given a set of points S={p1,. . ., pn} in Euclidean d -dimensional space, we address the problem of computing the d -dimensional annulus of smallest width containing the set. We give a complete characterization of the centers of annuli which are locally minimal in arbitrary dimension and we show that, for d=2 , a locally minimal annulus has two points on the inner circle and two points on the outer circle that interlace anglewise as seen from the center of the annulus. Using this characterization, we show that, given a circular order of the points, there is at most one locally minimal annulus consistent with that order and it can be computed in time O(n log n) using a simple algorithm. Furthermore, when points are in convex position, the problem can be solved in optimal Θ(n) time.