
We strengthen the connections between electrical transformations and homotopy
from the planar settingobserved and studied since Steinitzto arbitrary
surfaces with punctures. As a result, we improve our earlier lower bound on the
number of electrical transformations required to reduce an $n$vertex graph on
surface in the worst case [SOCG 2016] in two different directions. Our previous
$\Omega(n^{3/2})$ lower bound applies only to facial electrical transformations
on plane graphs with no terminals. First we provide a stronger $\Omega(n^2)$
lower bound when the planar graph has two or more terminals, which follows from
a quadratic lower bound on the number of homotopy moves in the annulus. Our
second result extends our earlier $\Omega(n^{3/2})$ lower bound to the wider
class of planar electrical transformations, which preserve the planarity of the
graph but may delete cycles that are not faces of the given embedding. This new
lower bound follows from the observation that the defect of the medial graph of
a planar graph is the same for all its planar embeddings.

We show that if a graph $G$ with $n \geq 3$ vertices can be drawn in the
plane such that each of its edges is involved in at most four crossings, then
$G$ has at most $6n12$ edges. This settles a conjecture of Pach,
Radoi\v{c}i\'{c}, Tardos, and T\'oth, and yields a better bound for the famous
Crossing Lemma: The crossing number, $\mbox{cr}(G)$, of a (not too sparse)
graph $G$ with $n$ vertices and $m$ edges is at least $c\frac{m^3}{n^2}$, where
$c > 1/29$. This bound is known to be tight, apart from the constant $c$ for
which the previous best lower bound was $1/31.1$. As another corollary we
obtain some progress on the Albertson conjecture: Albertson conjectured that if
the chromatic number of a graph $G$ is $r$, then $\mbox{cr}(G) \geq
\mbox{cr}(K_r)$. This was verified by Albertson, Cranston, and Fox for $r \leq
12$, and for $r \leq 16$ by Bar\'at and T\'oth. Our results imply that
Albertson conjecture holds for $r \leq 18$.

Persistent homology, a central tool of topological data analysis, provides
invariants of data called barcodes (also known as persistence diagrams). A
barcode is simply a multiset of real intervals. Recent work of Edelsbrunner,
Jablonski, and Mrozek suggests an equivalent description of barcodes as
functors R > Mch, where R is the poset category of real numbers and Mch is the
category whose objects are sets and whose morphisms are matchings (i.e.,
partial injective functions). Such functors form a category Mch^R whose
morphisms are the natural transformations. Thus, this interpretation of
barcodes gives us a hitherto unstudied categorical structure on barcodes. The
aim of this note is to show that this categorical structure leads to
surprisingly simple reformulations of both the wellknown stability theorem for
persistent homology and a recent generalization called the induced matching
theorem.

For a set of points in the plane and a fixed integer $k > 0$, the Yao graph
$Y_k$ partitions the space around each point into $k$ equiangular cones of
angle $\theta=2\pi/k$, and connects each point to a nearest neighbor in each
cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether
or not they are geometric spanners. In this paper we close this gap by showing
that for odd $k \geq 5$, the spanning ratio of $Y_k$ is at most
$1/(12\sin(3\theta/8))$, which gives the first constant upper bound for $Y_5$,
and is an improvement over the previous bound of $1/(12\sin(\theta/2))$ for
odd $k \geq 7$. We further reduce the upper bound on the spanning ratio for
$Y_5$ from $10.9$ to $2+\sqrt{3} \approx 3.74$, which falls slightly below the
lower bound of $3.79$ established for the spanning ratio of $\Theta_5$
($\Theta$graphs differ from Yao graphs only in the way they select the closest
neighbor in each cone). This is the first such separation between a Yao and
$\Theta$graph with the same number of cones. We also give a lower bound of
$2.87$ on the spanning ratio of $Y_5$. Finally, we revisit the $Y_6$ graph,
which plays a particularly important role as the transition between the graphs
($k > 6$) for which simple inductive proofs are known, and the graphs ($k \le
6$) whose best spanning ratios have been established by complex arguments. Here
we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting
closer to the spanning ratio of 2 established for $\Theta_6$.

Knot and link diagrams are projections of one or more 3dimensional simple
closed curves into $R^2$, such that no more than two points project to the same
point in $R^2$. These diagrams are drawings of 4regular plane multigraphs.
Knots are typically smooth curves in $R^3$, so their projections should be
smooth curves in $R^2$ with good continuity and large crossing angles: exactly
the properties of Lombardi graph drawings (defined by circulararc edges and
perfect angular resolution).
We show that several knots do not allow plane Lombardi drawings. On the other
hand, we identify a large class of 4regular plane multigraphs that do have
Lombardi drawings. We then study two relaxations of Lombardi drawings and show
that every knot admits a plane 2Lombardi drawing (where edges are composed of
two circular arcs). Further, every knot is nearLombardi, that is, it can be
drawn as Lombardi drawing when relaxing the angular resolution requirement by
an arbitrary small angular offset $\varepsilon$, while maintaining a
$180^\circ$ angle between opposite edges.

We present a novel algorithm for deciding whether a given planar curve is an
image of a given spatial curve, obtained by a central or a parallel projection
with unknown parameters. The motivation comes from the problem of establishing
a correspondence between an object and an image, taken by a camera with unknown
position and parameters. A straightforward approach to this problem consists of
setting up a system of conditions on the projection parameters and then
checking whether or not this system has a solution. The computational advantage
of the algorithm presented here, in comparison to algorithms based on the
straightforward approach, lies in a significant reduction of a number of real
parameters that need to be eliminated in order to establish existence or
nonexistence of a projection that maps a given spatial curve to a given planar
curve. Our algorithm is based on projection criteria that reduce the projection
problem to a certain modification of the equivalence problem of planar curves
under affine and projective transformations. To solve the latter problem we
make an algebraic adaptation of signature construction that has been used to
solve the equivalence problems for smooth curves. We introduce a notion of a
classifying set of rational differential invariants and produce explicit
formulas for such invariants for the actions of the projective and the affine
groups on the plane.

Classic cakecutting algorithms enable people with different preferences to
divide among them a heterogeneous resource (``cake''), such that the resulting
division is fair according to each agent's individual preferences. However,
these algorithms either ignore the geometry of the resource altogether, or
assume it is onedimensional. In practice, it is often required to divide
multidimensional resources, such as landestates or advertisement spaces in
print or electronic media. In such cases, the geometric shape of the allotted
piece is of crucial importance. For example, when building houses or designing
advertisements, in order to be useful, the allotments should be squares or
rectangles with bounded aspectratio. We thus introduce the problem of fair
land division  fair division of a multidimensional resource wherein the
allocated piece must have a prespecified geometric shape. We present
constructive division algorithms that satisfy the two most prominent fairness
criteria, namely envyfreeness and proportionality. In settings where
proportionality cannot be achieved due to the geometric constraints, our
algorithms provide a partiallyproportional division, guaranteeing that the
fraction allocated to each agent be at least a certain positive constant. We
prove that in many natural settings the envyfreeness requirement is compatible
with the best attainable partialproportionality.

Let $A$ be an $(m \times n)$ integral matrix, and let $P=\{ x : A x \leq b\}$
be an $n$dimensional polytope. The width of $P$ is defined as $ w(P)=min\{
x\in \mathbb{Z}^n\setminus\{0\} :\: max_{x \in P} x^\top u  min_{x \in P}
x^\top v \}$. Let $\Delta(A)$ and $\delta(A)$ denote the greatest and the
smallest absolute values of a determinant among all $r(A) \times r(A)$
submatrices of $A$, where $r(A)$ is the rank of a matrix $A$. We prove that if
every $r(A) \times r(A)$ submatrix of $A$ has a determinant equal to $\pm
\Delta(A)$ or $0$ and $w(P)\ge (\Delta(A)1)(n+1)$, then $P$ contains $n$
affine independent integer points. Also we have similar results for the case of
\emph{$k$modular} matrices. The matrix $A$ is called \emph{totally
$k$modular} if every square submatrix of $A$ has a determinant in the set
$\{0,\, \pm k^r :\: r \in \mathbb{N} \}$. When $P$ is a simplex and $w(P)\ge
\delta(A)1$, we describe a polynomial time algorithm for finding an integer
point in $P$. Finally we show that if $A$ is \emph{almost unimodular}, then
integer program $\max \{c^\top x :\: x \in P \cap \mathbb{Z}^n \}$ can be
solved in polynomial time. The matrix $A$ is called \emph{almost unimodular} if
$\Delta(A) \leq 2$ and any $(r(A)1)\times(r(A)1)$ submatrix has a
determinant from the set $\{0,\pm 1\}$.

Given $n$ pairwise openly disjoint triangles in 3space, their vertical depth
relation may contain cycles. We show that, for any $\varepsilon>0$, the
triangles can be cut into $O(n^{3/2+\varepsilon})$ connected semialgebraic
pieces, whose description complexity depends only on the choice of
$\varepsilon$, such that the depth relation among these pieces is now a proper
partial order. This bound is nearly tight in the worst case. We are not aware
of any previous study of this problem, in this full generality, with a
subquadratic bound on the number of pieces.
This work extends the recent study by two of the authors (Aronov,
Sharir~2018) on eliminating depth cycles among lines in 3space. Our approach
is again algebraic, and makes use of a recent variant of the polynomial
partitioning technique, due to Guth, which leads to a recursive procedure for
cutting the triangles. In contrast to the case of lines, our analysis here is
considerably more involved, due to the twodimensional nature of the objects
being cut, so additional tools, from topology and algebra, need to be brought
to bear.
Our result essentially settles a 35yearold open problem in computational
geometry, motivated by hiddensurface removal in computer graphics.

We introduce the family of $k$gapplanar graphs for $k \geq 0$, i.e., graphs
that have a drawing in which each crossing is assigned to one of the two
involved edges and each edge is assigned at most $k$ of its crossings. This
definition is motivated by applications in edge casing, as a $k$gapplanar
graph can be drawn crossingfree after introducing at most $k$ local gaps per
edge. We present results on the maximum density of $k$gapplanar graphs, their
relationship to other classes of beyondplanar graphs, characterization of
$k$gapplanar complete graphs, and the computational complexity of recognizing
$k$gapplanar graphs.

We show that the Radon number characterizes the existence of weak nets in
separable convexity spaces (an abstraction of the euclidean notion of
convexity). The construction of weak nets when the Radon number is finite is
based on Helly's property and on metric properties of VC classes. The lower
bound on the size of weak nets when the Radon number is large relies on the
chromatic number of the Kneser graph. As an application, we prove a
boostingtype result for weak $\epsilon$nets.

Many algorithms in machine learning and computational geometry require, as
input, the intrinsic dimension of the manifold that supports the probability
distribution of the data. This parameter is rarely known and therefore has to
be estimated. We characterize the statistical difficulty of this problem by
deriving upper and lower bounds on the minimax rate for estimating the
dimension. First, we consider the problem of testing the hypothesis that the
support of the datagenerating probability distribution is a wellbehaved
manifold of intrinsic dimension $d_1$ versus the alternative that it is of
dimension $d_2$, with $d_{1}<d_{2}$. With an i.i.d. sample of size $n$, we
provide an upper bound on the probability of choosing the wrong dimension of
$O\left( n^{\left(d_{2}/d_{1}1\epsilon\right)n} \right)$, where $\epsilon$
is an arbitrarily small positive number. The proof is based on bounding the
length of the traveling salesman path through the data points. We also
demonstrate a lower bound of $\Omega \left( n^{(2d_{2}2d_{1}+\epsilon)n}
\right)$, by applying Le Cam's lemma with a specific set of $d_{1}$dimensional
probability distributions. We then extend these results to get minimax rates
for estimating the dimension of wellbehaved manifolds. We obtain an upper
bound of order $O \left( n^{(\frac{1}{m1}\epsilon)n} \right)$ and a lower
bound of order $\Omega \left( n^{(2+\epsilon)n} \right)$, where $m$ is the
embedding dimension.

We present in this paper a generic and parameterfree algorithm to
efficiently build a wide variety of optical components, such as mirrors or
lenses, that satisfy some light energy constraints. In all of our problems, one
is given a collimated or point light source and a desired illumination after
reflection or refraction and the goal is to design the geometry of a mirror or
lens which transports exactly the light emitted by the source onto the target.
We first propose a general framework and show that eight different optical
component design problems amount to solving a light energy conservation
equation that involves the computation of visibility diagrams. We then show
that these diagrams all have the same structure and can be obtained by
intersecting a 3D Power diagram with a planar or spherical domain. This allows
us to propose an efficient and fully generic algorithm capable to solve these
eight optical component design problems. The support of the prescribed target
illumination can be a set of directions or a set of points located at a finite
distance. Our solutions satisfy design constraints such as convexity or
concavity. We show the effectiveness of our algorithm on simulated and
fabricated examples.

Persistence diagrams are common objects in the field of Topological Data
Analysis. They are topological summaries that capture both topological and
geometric structure within data. Recently there has been a surge of interest in
developing tools to statistically analyse populations of persistence diagrams,
a process hampered by the complicated geometry of the space of persistence
diagrams. In this paper we study the median of a set of diagrams, defined as
the minimizer of an appropriate cost function analogous to the sum of distances
used for samples of real numbers. We then characterize the local minima of this
cost function and in doing so characterize the median. We also do some
comparative analysis of the properties of the median and the mean.

A point visibility graph is a graph induced by a set of points in the plane,
where every vertex corresponds to a point, and two vertices are adjacent
whenever the two corresponding points are visible from each other, that is, the
open segment between them does not contain any other point of the set. We study
the recognition problem for point visibility graphs: given a simple undirected
graph, decide whether it is the visibility graph of some point set in the
plane. We show that the problem is complete for the existential theory of the
reals. Hence the problem is as hard as deciding the existence of a real
solution to a system of polynomial inequalities. The proof involves simple
substructures forcing collinearities in all realizations of some visibility
graphs, which are applied to the algebraic universality constructions of Mn\"ev
and RichterGebert. This solves a longstanding open question and paves the way
for the analysis of other classes of visibility graphs. Furthermore, as a
corollary of one of our construction, we show that there exist point visibility
graphs that do not admit any geometric realization with points having integer
coordinates.

As a generalization of the use of graphs to describe pairwise interactions,
simplicial complexes can be used to model higherorder interactions between
three or more objects in complex systems. There has been a recent surge in
activity for the development of data analysis methods applicable to simplicial
complexes, including techniques based on computational topology, higherorder
random processes, generalized Cheeger inequalities, isoperimetric inequalities,
and spectral methods. In particular, spectral learning methods (e.g. label
propagation and clustering) that directly operate on simplicial complexes
represent a new direction for analyzing such complex datasets.
To apply spectral learning methods to massive datasets modeled as simplicial
complexes, we develop a method for sparsifying simplicial complexes that
preserves the spectrum of the associated Laplacian matrices. We show that the
theory of Spielman and Srivastava for the sparsification of graphs extends to
simplicial complexes via the up Laplacian. In particular, we introduce a
generalized effective resistance for simplices, provide an algorithm for
sparsifying simplicial complexes at a fixed dimension, and give a specific
version of the generalized Cheeger inequality for weighted simplicial
complexes. Finally, we introduce higherorder generalizations of spectral
clustering and label propagation for simplicial complexes and demonstrate via
experiments the utility of the proposed spectral sparsification method for
these applications.

We show that the Cheeger constant for $n$dimensional isotropic logconcave
measures is $O(n^{1/4})$, improving on the previous best bound of
$O(n^{1/3}\sqrt{\log n}).$ As corollaries we obtain the same improved bound on
the thinshell estimate, Poincar\'{e} constant and Lipschitz concentration
constant and an alternative proof of this bound for the isotropic (slicing)
constant; it also follows that the ball walk for sampling from an isotropic
logconcave density in ${\bf R}^{n}$ converges in $O^{*}(n^{2.5})$ steps from a
warm start. The proof is based on gradually transforming any logconcave density
to one that has a significant Gaussian factor via a Martingale process.
Extending this proof technique, we prove that the logSobolev constant of any
isotropic logconcave density in ${\bf R}^{n}$ with support of diameter $D$ is
$\Omega(1/D)$, resolving a question posed by Frieze and Kannan in 1997. This is
asymptotically the best possible estimate and improves on the previous bound of
$\Omega(1/D^{2})$ by KannanLov\'{a}szMontenegro. It follows that for any
isotropic logconcave density, the ball walk with step size
$\delta=\Theta(1/\sqrt{n})$ mixes in $O\left(n^{2}D\right)$ proper steps from
\emph{any }starting point. This improves on the previous best bound of
$O(n^{2}D^{2})$ and is also asymptotically tight.
The new bound leads to the following large deviation inequality for an
$L$Lipschitz function $g$ over an isotropic logconcave density $p$: for any
$t>0$, \[ Pr_{x\sim p}\left(\leftg(x)\bar{g}\right\geq L\cdot
t\right)\leq\exp(\frac{c\cdot t^{2}}{t+\sqrt{n}}) \] where $\bar{g}$ is the
median or mean of $g$ for $x\sim p$; this generalizes and improves on previous
bounds by Paouris and by GuedonMilman. The technique also bounds the ``small
ball'' probability in terms of the Cheeger constant, and recovers the current
best bound.

A geographic network is a graph whose vertices are restricted to lie in a
prescribed region in the plane. In this paper we begin to study the following
fundamental problem for geographic networks: can a given geographic network be
drawn without crossings? We focus on the seemingly simple setting where each
region is a vertical segment, and one wants to connect pairs of segments with a
path that lies inside the convex hull of the two segments. We prove that when
paths must be drawn as straight line segments, it is NPcomplete to determine
if a crossingfree solution exists, even if all vertical segments have unit
length. In contrast, we show that when paths must be monotone curves, the
question can be answered in polynomial time. In the more general case of paths
that can have any shape, we show that the problem is polynomial under certain
assumptions.

We say that a finite set of red and blue points in the plane in general
position can be $K_{1,3}$covered if the set can be partitioned into subsets of
size $4$, with $3$ points of one color and $1$ point of the other color, in
such a way that, if at each subset the fourth point is connected by
straightline segments to the samecolored points, then the resulting set of
all segments has no crossings. We consider the following problem: Given a set
$R$ of $r$ red points and a set $B$ of $b$ blue points in the plane in general
position, how many points of $R\cup B$ can be $K_{1,3}$covered? and we prove
the following results:
(1) If $r=3g+h$ and $b=3h+g$, for some nonnegative integers $g$ and $h$,
then there are point sets $R\cup B$, like $\{1,3\}$equitable sets (i.e.,
$r=3b$ or $b=3r$) and linearly separable sets, that can be $K_{1,3}$covered.
(2) If $r=3g+h$, $b=3h+g$ and the points in $R\cup B$ are in convex position,
then at least $r+b4$ points can be $K_{1,3}$covered, and this bound is tight.
(3) There are arbitrarily large point sets $R\cup B$ in general position,
with $r=b+1$, such that at most $r+b5$ points can be $K_{1,3}$covered.
(4) If $b\le r\le 3b$, then at least $\frac{8}{9}(r+b8)$ points of $R\cup B$
can be $K_{1,3}$covered. For $r>3b$, there are too many red points and at
least $r3b$ of them will remain uncovered in any $K_{1,3}$covering.
Furthermore, in all the cases we provide efficient algorithms to compute the
corresponding coverings.

In the Planar 3SAT problem, we are given a 3SAT formula together with its
incidence graph, which is planar, and are asked whether this formula is
satisfiable. Since Lichtenstein's proof that this problem is NPcomplete, it
has been used as a starting point for a large number of reductions. In the
course of this research, different restrictions on the incidence graph of the
formula have been devised, for which the problem also remains hard.
In this paper, we investigate the restriction in which we require that the
incidence graph can be augmented by the edges of a Hamiltonian cycle that first
passes through all variables and then through all clauses, in a way that the
resulting graph is still planar. We show that the problem of deciding
satisfiability of a 3SAT formula remains NPcomplete even if the incidence
graph is restricted in that way and the Hamiltonian cycle is given. This
complements previous results demanding cycles only through either the variables
or clauses.
The problem remains hard for monotone formulas, as well as for instances with
exactly three distinct variables per clause. In the course of this
investigation, we show that monotone instances of Planar 3SAT with exactly
three distinct variables per clause are always satisfiable, thus settling the
question by Darmann, D\"ocker, and Dorn on the complexity of this problem
variant in a surprising way.

We introduce the fullydynamic conflictfree coloring problem for a set $S$
of intervals in $\mathbb{R}^1$ with respect to points, where the goal is to
maintain a conflictfree coloring for$S$ under insertions and deletions. A
coloring is conflictfree if for each point $p$ contained in some interval, $p$
is contained in an interval whose color is not shared with any other interval
containing $p$. We investigate tradeoffs between the number of colors used and
the number of intervals that are recolored upon insertion or deletion of an
interval. Our results include:
 a lower bound on the number of recolorings as a function of the number of
colors, which implies that with $O(1)$ recolorings per update the worstcase
number of colors is $\Omega(\log n/\log\log n)$, and that any strategy using
$O(1/\varepsilon)$ colors needs $\Omega(\varepsilon n^{\varepsilon})$
recolorings;
 a coloring strategy that uses $O(\log n)$ colors at the cost of $O(\log n)$
recolorings, and another strategy that uses $O(1/\varepsilon)$ colors at the
cost of $O(n^{\varepsilon}/\varepsilon)$ recolorings;
 stronger upper and lower bounds for special cases.
We also consider the kinetic setting where the intervals move continuously
(but there are no insertions or deletions); here we show how to maintain a
coloring with only four colors at the cost of three recolorings per event and
show this is tight.

The hyperbolic random graph model (HRG) has proven useful in the analysis of
scalefree networks, which are ubiquitous in many fields, from social network
analysis to biology. However, working with this model is algorithmically and
conceptually challenging because of the nature of the distances in the
hyperbolic plane. In this paper we study the algorithmic properties of
regularly generated triangulations in the hyperbolic plane. We propose a
discrete variant of the HRG model where nodes are mapped to the vertices of
such a triangulation; our algorithms allow us to work with this model in a
simple yet efficient way. We present experimental results conducted on real
world networks to evaluate the practical benefits of DHRG in comparison to the
HRG model.

We revisit the online Unit Clustering and Unit Covering problems in higher
dimensions: Given a set of $n$ points in a metric space, that arrive one by
one, Unit Clustering asks to partition the points into the minimum number of
clusters (subsets) of diameter at most one; while Unit Covering asks to cover
all points by the minimum number of balls of unit radius. In this paper, we
work in $\mathbb{R}^d$ using the $L_\infty$ norm.
We show that the competitive ratio of any online algorithm (deterministic or
randomized) for Unit Clustering must depend on the dimension $d$. We also give
a randomized online algorithm with competitive ratio $O(d^2)$ for Unit
Clustering}of integer points (i.e., points in $\mathbb{Z}^d$, $d\in
\mathbb{N}$, under $L_{\infty}$ norm). We show that the competitive ratio of
any deterministic online algorithm for Unit Covering is at least $2^d$. This
ratio is the best possible, as it can be attained by a simple deterministic
algorithm that assigns points to a predefined set of unit cubes. We complement
these results with some additional lower bounds for related problems in higher
dimensions.

We describe and analyze an algorithm for computing the homology (Betti
numbers and torsion coefficients) of basic semialgebraic sets which works in
weak exponential time. That is, out of a set of exponentially small measure in
the space of data the cost of the algorithm is exponential in the size of the
data. All algorithms previously proposed for this problem have a complexity
which is doubly exponential (and this is so for almost all data).

In this paper we study the relationship between a very classical algebraic
object associated to a filtration of spaces, namely a spectral sequence
introduced by Leray in the 1940's, and a more recently invented object that has
found many applications  namely, its persistent homology groups. We show the
existence of a long exact sequence of groups linking these two objects and
using it derive formulas expressing the dimensions of each individual groups of
one object in terms of the dimensions of the groups in the other object. The
main tool used to mediate between these objects is the notion of exact couples
first introduced by Massey in 1952.