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 .     

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.     

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.     

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.     

Approximating Tverberg Points in Linear Time for Any Fixed Dimension

Let $P \subseteq \mathbb{R }^d$ P ? R d be a $d$ d -dimensional $n$ n -point set. A Tverberg partition is a partition of $P$ P into $r$ r sets $P_1, \dots , P_r$ P 1 , ? , P r such that the convex hulls $\hbox {conv}(P_1), \dots , \hbox {conv}(P_r)$ conv ( P 1 ) , ? , conv ( P r ) have non-empty intersection. A point in $\bigcap _{i=1}^{r} \hbox {conv}(P_i)$ ? i = 1 r conv ( P i ) is called a Tverberg point of depth $r$ r for $P$ P . A classic result by Tverberg shows that there always exists a Tverberg partition of size $\lceil n/(d+1) \rceil $ ? n / ( d + 1 ) ? , but it is not known how to find such a partition in polynomial time. Therefore, approximate solutions are of interest. We describe a deterministic algorithm that finds a Tverberg partition of size $\lceil n/4(d+1)^3 \rceil $ ? n / 4 ( d + 1 ) 3 ? in time $d^{O(\log d)} n$ d O ( log d ) n . This means that for every fixed dimension we can compute an approximate Tverberg point (and hence also an approximate centerpoint) in linear time. Our algorithm is obtained by combining a novel lifting approach with a recent result by Miller and Sheehy (Comput Geom Theory Appl 43(8):647–654, 2010).     

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 .     

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.     

On Sets Defining Few Ordinary Lines

Let $P$ P be a set of $n$ n points in the plane, not all on a line. We show that if $n$ n is large then there are at least $n/2$ n / 2 ordinary lines, that is to say lines passing through exactly two points of $P$ P . This confirms, for large $n$ n , a conjecture of Dirac and Motzkin. In fact we describe the exact extremisers for this problem, as well as all sets having fewer than $n-C$ n - C ordinary lines for some absolute constant $C$ C . We also solve, for large $n$ n , the “orchard-planting problem”, which asks for the maximum number of lines through exactly 3 points of $P$ P . Underlying these results is a structure theorem which states that if $P$ P has at most $Kn$ K n ordinary lines then all but O(K) points of $P$ P lie on a cubic curve, if $n$ n is sufficiently large depending on $K$ K .     

Many Collinear k-Tuples with no k+1 Collinear Points

For every $k>3$ k > 3 , we give a construction of planar point sets with many collinear $k$ k -tuples and no collinear $(k+1)$ ( k + 1 ) -tuples. We show that there are $n_0=n_0(k)$ n 0 = n 0 ( k ) and $c=c(k)$ c = c ( k ) such that if $n\ge n_0$ n ≥ n 0 , then there exists a set of $n$ n points in the plane that does not contain $k+1$ k + 1 points on a line, but it contains at least $n^{2-({c}/{\sqrt{\log n}})}$ n 2 - ( c / log n ) collinear $k$ k -tuples of points. Thus, we significantly improve the previously best known lower bound for the largest number of collinear $k$ k -tuples in such a set, and get reasonably close to the trivial upper bound $O(n^2)$ O ( n 2 ) .     

Solving maximum clique in sparse graphs: an O(nm+n2^{d/4}) algorithm for d-degenerate graphs

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy \(d\) . The algorithm runs in \(O\left( nm+n T_d \right) \) time, where \(T_d\) is the time to solve the maximum clique problem in an arbitrary graph on \(d\) vertices. The best bound as of now is \(T_d=O(2^{d/4})\) by Robson. This shows that the maximum clique problem is solvable in \(O(nm)\) time in graphs for which \(d \le 4 \log _2 m + O(1)\) . The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in \(2^{O(\sqrt{n})}\) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.     

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).     

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 .     

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 .     

A Question from a Famous Paper of Erdős

Given a convex body $K$ K , consider the smallest number $N$ N so that there is a point $P\in \partial K$ P ∈ ? K such that every circle centred at $P$ P intersects $\partial K$ ? K in at most $N$ N points. In 1946 Erd?s conjectured that $N=2$ N = 2 for all $K$ K , but there are convex bodies for which this is not the case. As far as we know there is no known global upper bound. We show that no convex body has $N=\infty $ N = ∞ and that there are convex bodies for which $N = 6$ N = 6 .     

Characterization of Co-blockers for Simple Perfect Matchings in a Convex Geometric Graph

Consider the complete convex geometric graph on $2m$ 2 m vertices, CGG $(2m)$ ( 2 m ) , i.e., the set of all boundary edges and diagonals of a planar convex $2m$ 2 m -gon P. In (Keller and Perles, Israel J Math 187:465–484, 2012), the smallest sets of edges that meet all the simple perfect matchings (SPMs) in CGG $(2m)$ ( 2 m ) (called “blockers”) are characterized, and it is shown that all these sets are caterpillar graphs with a special structure, and that their total number is $m \cdot 2^{m-1}$ m · 2 m ? 1 . In this paper we characterize the co-blockers for SPMs in CGG $(2m)$ ( 2 m ) , that is, the smallest sets of edges that meet all the blockers. We show that the co-blockers are exactly those perfect matchings M in CGG $(2m)$ ( 2 m ) where all edges are of odd order, and two edges of M that emanate from two adjacent vertices of P never cross. In particular, while the number of SPMs and the number of blockers grow exponentially with m, the number of co-blockers grows super-exponentially.     

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.     

Size of Components of a Cube Coloring

Suppose a d-dimensional lattice cube of size $n^d$ n d is colored in several colors so that no face of its triangulation (subdivision of the standard partition into $n^d$ n d small cubes) is colored in $m+2$ m + 2 colors. Then one color is used at least $f(d, m) n^{d-m}$ f ( d , m ) n d ? m times.     

Algebraic Boundaries of \mathrm{SO}(2)-Orbitopes

Let $X\subset \mathbb{A }^{2r}$ X ? A 2 r be a real curve embedded into an even-dimensional affine space. We characterise when the $r$ r th secant variety to $X$ X is an irreducible component of the algebraic boundary of the convex hull of the real points $X(\mathbb{R })$ X ( R ) of $X$ X . This fact is then applied to $4$ 4 -dimensional $\mathrm{SO}(2)$ SO ( 2 ) -orbitopes and to the so called Barvinok–Novik orbitopes to study when they are basic closed semi-algebraic sets. In the case of $4$ 4 -dimensional $\mathrm{SO}(2)$ SO ( 2 ) -orbitopes, we find all irreducible components of their algebraic boundary.     

Many Empty Triangles have a Common Edge

Given a finite point set $X$ X in the plane, the degree of a pair $\{x,y\} \subset X$ { x , y } ? X is the number of empty triangles $t=\mathrm {conv} \{x,y,z\},$ t = conv { x , y , z } , where empty means $t\cap X=\{x,y,z\}.$ t ∩ X = { x , y , z } . Define $\deg X$ deg X as the maximal degree of a pair in $X.$ X . Our main result is that if $X$ X is a random sample of $n$ n independent and uniform points from a fixed convex body, then $\deg X \ge cn/\ln n$ deg X ≥ cn / ln n in expectation.     

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.