On Topological Changes in the Delaunay Triangulation of Moving Points

Let $P$ P be a collection of $n$ n points moving along pseudo-algebraic trajectories in the plane. (So, in particular, there are constants $s,c>0$ s , c > 0 such that any four points are co-circular at most $s$ s times, and any three points are collinear at most $c$ c times.) One of the hardest open problems in combinatorial and computational geometry is to obtain a nearly quadratic upper bound, or at least a sub-cubic bound, on the maximum number of discrete changes that the Delaunay triangulation ${\mathrm{DT}}(P)$ DT ( P ) of $P$ P experiences during the motion of the points of $P$ P . In this paper, we obtain an upper bound of $O(n^{2+{\varepsilon }})$ O ( n 2 + ε ) , for any ${\varepsilon }>0$ ε > 0 , under the assumptions that (i) any four points can be co-circular at most twice and (ii) either no triple of points can be collinear more than twice or no ordered triple of points can be collinear more than once.     

Polytopal Affine Semigroups with Holes Deep Inside

Given a positive integer $k$ k , we construct a lattice $3$ 3 -simplex $P$ P with the following property: The affine semigroup $Q_P$ Q P associated to $P$ P is not normal, and every element $q \in \overline{Q}_P \setminus Q_P$ q ∈ Q ¯ P ? Q P has lattice distance at least $k$ k above every facet of $Q_P$ Q P .     

The 2-Page Crossing Number of K_{n}

Around 1958, Hill described how to draw the complete graph $K_n$ K n with $$\begin{aligned} Z(n) :=\frac{1}{4}\Big \lfloor \frac{n}{2}\Big \rfloor \Big \lfloor \frac{n-1}{2}\Big \rfloor \Big \lfloor \frac{n-2}{2}\Big \rfloor \Big \lfloor \frac{n-3}{2}\Big \rfloor \end{aligned}$$ Z ( n ) : = 1 4 ? n 2 ? ? n ? 1 2 ? ? n ? 2 2 ? ? n ? 3 2 ? crossings, and conjectured that the crossing number ${{\mathrm{cr}}}(K_{n})$ cr ( K n ) of $K_n$ K n is exactly $Z(n)$ Z ( n ) . This is also known as Guy’s conjecture as he later popularized it. Towards the end of the century, substantially different drawings of $K_{n}$ K n with $Z(n)$ Z ( n ) crossings were found. These drawings are 2-page book drawings, that is, drawings where all the vertices are on a line $\ell $ ? (the spine) and each edge is fully contained in one of the two half-planes (pages) defined by  $\ell $ ? . The 2-page crossing number of $K_{n} $ K n , denoted by $\nu _{2}(K_{n})$ ν 2 ( K n ) , is the minimum number of crossings determined by a 2-page book drawing of $K_{n}$ K n . Since ${{\mathrm{cr}}}(K_{n}) \le \nu _{2}(K_{n})$ cr ( K n ) ≤ ν 2 ( K n ) and $\nu _{2}(K_{n}) \le Z(n)$ ν 2 ( K n ) ≤ Z ( n ) , a natural step towards Hill’s Conjecture is the weaker conjecture $\nu _{2}(K_{n}) = Z(n)$ ν 2 ( K n ) = Z ( n ) , popularized by Vrt’o. In this paper we develop a new technique to investigate crossings in drawings of $K_{n}$ K n , and use it to prove that $\nu _{2}(K_{n}) = Z(n) $ ν 2 ( K n ) = Z ( n ) . To this end, we extend the inherent geometric definition of $k$ k -edges for finite sets of points in the plane to topological drawings of $K_{n}$ K n . We also introduce the concept of ${\le }{\le }k$ ≤ ≤ k -edges as a useful generalization of ${\le }k$ ≤ k -edges and extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of $K_{n}$ K n in terms of its number of ${\le }k$ ≤ k -edges to the topological setting. Finally, we give a complete characterization of crossing minimal 2-page book drawings of $K_{n}$ K n and show that, up to equivalence, they are unique for $n$ n even, but that there exist an exponential number of non homeomorphic such drawings for $n$ n odd.     

Entropy and Diffraction of the k-Free Points in n-Dimensional Lattices

We consider the $k$ k th-power-free points in $n$ n -dimensional lattices and explicitly calculate their entropies and diffraction spectra. This is of particular interest since these sets have holes of unbounded inradius.     

Maximal Equilateral Sets

A subset of a normed space $X$ X is called equilateral if the distance between any two points is the same. Let $m(X)$ m ( X ) be the smallest possible size of an equilateral subset of $X$ X maximal with respect to inclusion. We first observe that Petty’s construction of a $d$ d - $X$ X of any finite dimension $d\ge 4$ d ≥ 4 with $m(X)=4$ m ( X ) = 4 can be generalised to give $m(X\oplus _1\mathbb R )=4$ m ( X ⊕ 1 R ) = 4 for any $X$ X of dimension at least $2$ 2 which has a smooth point on its unit sphere. By a construction involving Hadamard matrices we then show that for any set $\Gamma $ Γ , $m(\ell _p(\Gamma ))$ m ( ? p ( Γ ) ) is finite and bounded above by a function of $p$ p , for all $1\le p<2$ 1 ≤ p < 2 . Also, for all $p\in [1,\infty )$ p ∈ [ 1 , ∞ ) and $d\in \mathbb N $ d ∈ N there exists $c=c(p,d)>1$ c = c ( p , d ) > 1 such that $m(X)\le d+1$ m ( X ) ≤ d + 1 for all $d$ d - $X$ X with Banach–Mazur distance less than $c$ c from $\ell _p^d$ ? p d . Using Brouwer’s fixed-point theorem we show that $m(X)\le d+1$ m ( X ) ≤ d + 1 for all $d$ d - $X$ X with Banach–Mazur distance less than $3/2$ 3 / 2 from $\ell _\infty ^d$ ? ∞ d . A graph-theoretical argument furthermore shows that $m(\ell _\infty ^d)=d+1$ m ( ? ∞ d ) = d + 1 . The above results lead us to conjecture that $m(X)\le 1+\dim X$ m ( X ) ≤ 1 + dim X for all finite-normed spaces $X$ X .     

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $X$ X in $\mathbb{R }^2$ R 2 that is not an axis-aligned rectangle and for any positive integer $k$ k produces a family $\mathcal{F }$ F of sets, each obtained by an independent horizontal and vertical scaling and translation of $X$ X , such that no three sets in $\mathcal{F }$ F pairwise intersect and $\chi (\mathcal{F })>k$ χ ( F ) > k . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.     

An Index Formula in Connection with Meromorphic Approximation

Let $\Phi $ be a continuous $n\times n$ matrix-valued function on the unit circle $\mathbb T $ such that the $(k-1)$ st singular value of the Hankel operator with symbol $\Phi $ is greater than the $k$ th singular value. In this case, it is well-known that $\Phi $ has a unique superoptimal meromorphic approximant $Q$ in $H^{\infty }_{(k)}$ ; that is, $Q$ has at most $k$ poles in the unit disc $\mathbb D $ (in the sense that the McMillan degree of $Q$ in $\mathbb D $ is at most $k$ ) and $Q$ minimizes the essential suprema of singular values $s_{j}\left((\Phi -Q)(\zeta )\right)\!, j\ge 0$ , with respect to the lexicographic ordering. For each $j\ge 0$ , the essential supremum of $s_{j}\left((\Phi -Q)(\zeta )\right)$ is called the $j$ th superoptimal singular value of degree $k$ of $\Phi $ . We prove that if $\Phi $ has $n$ non-zero superoptimal singular values of degree $k$ , then the Toeplitz operator $T_{\Phi -Q}$ with symbol $\Phi -Q$ is Fredholm and has index $$ \mathrm{ind}T_{\Phi -Q}=\dim \ker T_{\Phi -Q}=2k+\dim \mathcal E , $$ where $\mathcal E =\{ \xi \in \ker H_{Q}: \Vert H_{\Phi }\xi \Vert _{2}=\Vert (\Phi -Q)\xi \Vert _{2}\}$ and $H_{\Phi }$ denotes the Hankel operator with symbol $\Phi $ . This result can in fact be extended from continuous matrix-valued functions to the wider class of $k$ -admissible matrix-valued functions, i.e. essentially bounded $n\times n$ matrix-valued functions $\Phi $ on $\mathbb T $ for which the essential norm of the Hankel operator $H_{\Phi }$ is strictly less than the smallest non-zero superoptimal singular value of degree $k$ of $\Phi $ .     

Boundaries of Disk-Like Self-affine Tiles

Let $T:= T(A, \mathcal{D })$ T : = T ( A , D ) be a disk-like self-affine tile generated by an integral expanding matrix $A$ A and a consecutive collinear digit set $\mathcal{D }$ D , and let $f(x)=x^{2}+px+q$ f ( x ) = x 2 + px + q be the characteristic polynomial of $A$ A . In the paper, we identify the boundary $\partial T$ ? T with a sofic system by constructing a neighbor graph and derive equivalent conditions for the pair $(A,\mathcal{D })$ ( A , D ) to be a number system. Moreover, by using the graph-directed construction and a device of pseudo-norm $\omega $ ω , we find the generalized Hausdorff dimension $\dim _H^{\omega } (\partial T)=2\log \rho (M)/\log |q|$ dim H ω ( ? T ) = 2 log ρ ( M ) / log | q | where $\rho (M)$ ρ ( M ) is the spectral radius of certain contact matrix $M$ M . Especially, when $A$ A is a similarity, we obtain the standard Hausdorff dimension $\dim _H (\partial T)=2\log \rho /\log |q|$ dim H ( ? T ) = 2 log ρ / log | q | where $\rho $ ρ is the largest positive zero of the cubic polynomial $x^{3}-(|p|-1)x^{2}-(|q|-|p|)x-|q|$ x 3 ? ( | p | ? 1 ) x 2 ? ( | q | ? | p | ) x ? | q | , which is simpler than the known result.     

Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension

For a polyhedron $P$ P let $B(P)$ B ( P ) denote the polytopal complex that is formed by all bounded faces of $P$ P . If $P$ P is the intersection of $n$ n halfspaces in $\mathbb R ^D$ R D , but the maximum dimension $d$ d of any face in $B(P)$ B ( P ) is much smaller, we show that the combinatorial complexity of $P$ P cannot be too high; in particular, that it is independent of $D$ D . We show that the number of vertices of $P$ P is $O(n^d)$ O ( n d ) and the total number of bounded faces of the polyhedron is $O(n^{d^2})$ O ( n d 2 ) . For inputs in general position the number of bounded faces is $O(n^d)$ O ( n d ) . We show that for certain specific values of $d$ d and $D$ D , our bounds are tight. For any fixed $d$ d , we show how to compute the set of all vertices, how to determine the maximum dimension of a bounded face of the polyhedron, and how to compute the set of bounded faces in polynomial time, by solving a number of linear programs that is polynomial in  $n$ n .     

Improved Enumeration of Simple Topological Graphs

A simple topological graph $T=(V(T), E(T))$ T = ( V ( T ) , E ( T ) ) is a drawing of a graph in the plane where every two edges have at most one common point (an endpoint or a crossing) and no three edges pass through a single crossing. Topological graphs $G$ G and $H$ H are isomorphic if $H$ H can be obtained from $G$ G by a homeomorphism of the sphere, and weakly isomorphic if $G$ G and $H$ H have the same set of pairs of crossing edges. We generalize results of Pach and Tóth and the author’s previous results on counting different drawings of a graph under both notions of isomorphism. We prove that for every graph $G$ G with $n$ n vertices, $m$ m edges and no isolated vertices the number of weak isomorphism classes of simple topological graphs that realize $G$ G is at most $2^{O(n^2\log (m/n))}$ 2 O ( n 2 log ( m / n ) ) , and at most $2^{O(mn^{1/2}\log n)}$ 2 O ( m n 1 / 2 log n ) if $m\le n^{3/2}$ m ≤ n 3 / 2 . As a consequence we obtain a new upper bound $2^{O(n^{3/2}\log n)}$ 2 O ( n 3 / 2 log n ) on the number of intersection graphs of $n$ n pseudosegments. We improve the upper bound on the number of weak isomorphism classes of simple complete topological graphs with $n$ n vertices to $2^{n^2\cdot \alpha (n)^{O(1)}}$ 2 n 2 · α ( n ) O ( 1 ) , using an upper bound on the size of a set of permutations with bounded VC-dimension recently proved by Cibulka and the author. We show that the number of isomorphism classes of simple topological graphs that realize $G$ G is at most $2^{m^2+O(mn)}$ 2 m 2 + O ( m n ) and at least $2^{\Omega (m^2)}$ 2 Ω ( m 2 ) for graphs with $m>(6+\varepsilon )n$ m > ( 6 + ε ) n .     

The Geodesic Diameter of Polygonal Domains

This paper studies the geodesic diameter of polygonal domains having $h$ h holes and $n$ n corners. For simple polygons (i.e., $h=0$ h = 0 ), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as shown by Hershberger and Suri. For general polygonal domains with $h \ge 1$ h ≥ 1 , however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time $O(n^{7.73})$ O ( n 7.73 ) or $O(n^7 (\log n + h))$ O ( n 7 ( log n + h ) ) . The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.     

Tilings of Parallelograms with Similar Right Triangles

We say that a triangle $T$ T tiles the polygon $\mathcal A $ A if $\mathcal A $ A can be decomposed into finitely many non-overlapping triangles similar to $T$ T . A tiling is called regular if there are two angles of the triangles, say $\alpha $ α and $\beta $ β , such that at each vertex $V$ V of the tiling the number of triangles having $V$ V as a vertex and having angle $\alpha $ α at $V$ V is the same as the number of triangles having angle $\beta $ β at $V$ V . Otherwise the tiling is called irregular. Let $\mathcal P (\delta )$ P ( δ ) be a parallelogram with acute angle $\delta $ δ . In this paper we prove that if the parallelogram $\mathcal P (\delta )$ P ( δ ) is tiled with similar triangles of angles $(\alpha , \beta , \pi /2)$ ( α , β , π / 2 ) , then $(\alpha , \beta )=(\delta , \pi /2-\delta )$ ( α , β ) = ( δ , π / 2 - δ ) or $(\alpha , \beta )=(\delta /2, \pi /2-\delta /2)$ ( α , β ) = ( δ / 2 , π / 2 - δ / 2 ) , and if the tiling is regular, then only the first case can occur.     

An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $\mathcal D $ D , consisting of $n$ n tetrahedra with positive weights, and a real number $\varepsilon \in (0,1)$ ε ∈ ( 0 , 1 ) , our algorithm constructs paths in $\mathcal D $ D from a fixed source vertex to all vertices of $\mathcal D $ D , the costs of which are at most $1+\varepsilon $ 1 + ε times the costs of (weighted) shortest paths, in $O(\mathcal{C }(\mathcal D )\frac{n}{\varepsilon ^{2.5}}\log \frac{n}{\varepsilon }\log ^3\frac{1}{\varepsilon })$ O ( C ( D ) n ε 2.5 log n ε log 3 1 ε ) time, where $\mathcal{C }(\mathcal D )$ C ( D ) is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25–53, 2005), to three dimensions.     

Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain

In this paper, we study the problem of moving $n$ n sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an $O(n^2\log n)$ O ( n 2 log n ) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes $O(n^2)$ O ( n 2 ) time. We present an $O(n\log n)$ O ( n log n ) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes $O(n)$ O ( n ) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in $O(n)$ O ( n ) time, improving the previously best $O(n^2)$ O ( n 2 ) time solution.     

On the fast Khintchine spectrum in continued fractions

For $x\in [0,1)$ x ∈ [ 0 , 1 ) , let $x=[a_1(x), a_2(x),\ldots ]$ x = [ a 1 ( x ) , a 2 ( x ) , ... ] be its continued fraction expansion with partial quotients $\{a_n(x), n\ge 1\}$ { a n ( x ) , n ≥ 1 } . Let $\psi : \mathbb{N } \rightarrow \mathbb{N }$ ψ : N → N be a function with $\psi (n)/n\rightarrow \infty $ ψ ( n ) / n → ∞ as $n\rightarrow \infty $ n → ∞ . In this note, the fast Khintchine spectrum, i.e., the Hausdorff dimension of the set $$\begin{aligned} E(\psi ):=\left\{ x\in [0,1): \lim _{n\rightarrow \infty }\frac{1}{\psi (n)}\sum _{j=1}^n\log a_j(x)=1\right\} \end{aligned}$$ E ( ψ ) : = x ∈ [ 0 , 1 ) : lim n → ∞ 1 ψ ( n ) ∑ j = 1 n log a j ( x ) = 1 is completely determined without any extra condition on $\psi $ ψ . This fills a gap of the former work in Fan et al. (Ergod Theor Dyn Syst 29:73–109, 2009).     

On fluctuations of Riemann’s zeta zeros

It is shown that the normalized fluctuations of Riemann’s zeta zeros around their predicted locations follow the Gaussian law. It is also shown that fluctuations of two zeros, $\gamma _{k}$ and $\gamma _{k+x},$ with $x\sim \left( \log k\right) ^{\beta }, \beta >0,$ for large $k$ follow the two-variate Gaussian distribution with correlation $\left( 1-\beta \right) _{+}\! .$      

Partial regularity at the first singular time for hypersurfaces evolving by mean curvature

In this paper, we consider smooth, properly immersed hypersurfaces evolving by mean curvature in some open subset of   $\mathbb R ^{n+1}$ on a time interval $(0, t_0)$ . We prove that $p$ -integrability with $p\ge 2$ for the second fundamental form of these hypersurfaces in some space–time region $B_R(y)\times (0, t_0)$ implies that the $\mathcal H ^{n+2-p}$ -measure of the first singular set vanishes inside $B_R(y)$ . For $p=2$ and $n=2$ , this was established by Han and Sun. Our result furthermore generalizes previous work of Xu, Ye and Zhao and of Le and Sesum for $p\ge n+2$ , in which case the singular set was shown to be empty. By a theorem of Ilmanen, our integrability condition is satisfied for $p=2$ and $n=2\,$ if the initial surface has finite genus. Thus, the first singular set has zero $\mathcal H ^2$ -measure in this case. This is the conclusion of Brakke’s main regularity theorem for the special case of surfaces, but derived without having to impose the area continuity and unit density hypothesis. It follows from recent work of Head and of Huisken and Sinestrari that for the flow of closed, $k$ -convex hypersurfaces, that is hypersurfaces whose sum of the smallest $k$ principal curvatures is positive, our integrability criterion holds with exponent $p=n+3-k-\alpha $ for all small $\alpha >0$ as long as $1\le k\le n-1$ . Therefore, the first singular set of such solutions is at most $(k-1)$ -dimensional, which is an optimal estimate in view of some explicit examples.     

Solution of the Propeller Conjecture in \mathbb R ^3

It is shown that every measurable partition $\{A_1,\ldots , A_k\}$ { A 1 , … , A k } of $\mathbb R ^3$ R 3 satisfies 1 $$\begin{aligned} \sum _{i=1}^k\big \Vert \int _{A_i} x\mathrm{{e}}^{-\frac{1}{2}\Vert x\Vert _2^2}\mathrm{{d}}x\big \Vert _2^2\leqslant 9\pi ^2. \end{aligned}$$ ∑ i = 1 k ‖ ∫ A i x e - 1 2 ‖ x ‖ 2 2 d x ‖ 2 2 ? 9 π 2 . Let $\{P_1,P_2,P_3\}$ { P 1 , P 2 , P 3 } be the partition of $\mathbb R ^2$ R 2 into $120^{\circ }$ 120 ° sectors centered at the origin. The bound (1) is sharp, with equality holding if $A_i=P_i\times \mathbb R $ A i = P i × R for $i\in \{1,2,3\}$ i ∈ { 1 , 2 , 3 } and $A_i=\emptyset $ A i = ? for $i\in \{4,\ldots ,k\}$ i ∈ { 4 , … , k } . This settles positively the $3$ 3 -dimensional Propeller Conjecture of Khot and Naor [(Mathematika 55(1-2):129–165, 2009 (FOCS 2008)]. The proof of (1) reduces the problem to a finite set of numerical inequalities which are then verified with full rigor in a computer-assisted fashion. The main consequence (and motivation) of (1) is complexity-theoretic: the unique games hardness threshold of the kernel clustering problem with $4\times 4$ 4 × 4 centered and spherical hypothesis matrix equals $\frac{2\pi }{3}$ 2 π 3 .     

Recovering an Homogeneous Polynomial from Moments of Its Level Set

Let $\mathbf{K }:=\left\{ \mathbf{x }: g(\mathbf{x })\le 1\right\} $ K : = x : g ( x ) ≤ 1 be the compact (and not necessarily convex) sub-level set of some homogeneous polynomial $g$ g . Assume that the only knowledge about $\mathbf{K }$ K is the degree of $g$ g as well as the moments of the Lebesgue measure on $\mathbf{K }$ K up to order $2d$ 2 d . Then the vector of coefficients of $g$ g is the solution of a simple linear system whose associated matrix is nonsingular. In other words, the moments up to order $2d$ 2 d of the Lebesgue measure on $\mathbf{K }$ K encode all information on the homogeneous polynomial $g$ g that defines $\mathbf{K }$ K (in fact, only moments of order $d$ d and $2d$ 2 d are needed).