We study Snipperclips, a computer puzzle game whose objective is to create a target shape with two tools. The tools start as constant-complexity shapes, and each tool can snip (i.e., subtract its current shape from) the other tool. We study the compu
tational problem of, given a target shape represented by a polygonal domain of $n$ vertices, is it possible to create it as one of the tools shape via a sequence of snip operations? If so, how many snip operations are required? We consider several variants of the problem (such as allowing the tools to be disconnected and/or using an undo operation) and bound the number of operations needed for each of the variants.
Weak unit disk contact graphs are graphs that admit a representation of the nodes as a collection of internally disjoint unit disks whose boundaries touch if there is an edge between the corresponding nodes. We provide a gadget-based reduction to sho
w that recognizing embedded caterpillars that admit a weak unit disk contact representation is NP-hard.
Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its complement contains exactly one of the sites. We prove that it is NP-har
d to find a minimum-length sona drawing for $n$ given points, and that such a curve can be longer than the TSP tour of the same points by a factor $> 1.5487875$. When restricted to tours that lie on the edges of a square grid, with points in the grid cells, we prove that it is NP-hard even to decide whether such a tour exists. These results answer questions posed at CCCG 2006.
We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in $mathbb{Z}^d$. The construction must be {em consistent} (that is, satisfy the natural extension of the Euclidean
axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with $Theta(log N)$ error, where resemblance between segments is measured with the Hausdorff distance, and $N$ is the $L_1$ distance between the two points. This construction was considered tight because of a $Omega(log N)$ lower bound that applies to any consistent construction in $mathbb{Z}^2$. In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in $d$ dimensions must have $Omega(log^{1/(d-1)} N)$ error. We tie the error of a consistent construction in high dimensions to the error of similar {em weak} constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with $o(log N)$ error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. In order to show our lower bound, we also consider a colored variation of the concept of discrepancy of a set of points that we find of independent interest.
The classic Ham-Sandwich theorem states that for any $d$ measurable sets in $mathbb{R}^d$, there is a hyperplane that bisects them simultaneously. An extension by Barany, Hubard, and Jeronimo [DCG 2008] states that if the sets are convex and emph{wel
l-separated}, then for any given $alpha_1, dots, alpha_d in [0, 1]$, there is a unique oriented hyperplane that cuts off a respective fraction $alpha_1, dots, alpha_d$ from each set. Steiger and Zhao [DCG 2010] proved a discrete analogue of this theorem, which we call the emph{$alpha$-Ham-Sandwich theorem}. They gave an algorithm to find the hyperplane in time $O(n (log n)^{d-3})$, where $n$ is the total number of input points. The computational complexity of this search problem in high dimensions is open, quite unlike the complexity of the Ham-Sandwich problem, which is now known to be PPA-complete (Filos-Ratsikas and Goldberg [STOC 2019]). Recently, Fearley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new sub-class of CLS (Continuous Local Search) called emph{Unique End-of-Potential Line} (UEOPL). This class captures problems in CLS that have unique solutions. We show that for the $alpha$-Ham-Sandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL. This gives the first non-trivial containment of the problem in a complexity class and places it in the company of classic search problems such as finding the fixed point of a contraction map, the unique sink orientation problem and the $P$-matrix linear complementarity problem.
Ailon et al. [SICOMP11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,cdots,x_n$ follow some unknown emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $ma
thsf{D}_i$, and the $x_i$s are drawn independently. After spending $O(n^{1+varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/varepsilon)$, where $H in {H_mathrm{S},H_mathrm{DT}}$, and $H_mathrm{S}$ and $H_mathrm{DT}$ are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the $x_i$s under the emph{group product distribution}. There is a hidden partition of $[1,n]$ into groups; the $x_i$s in the $k$-th group are fixed unknown functions of the same hidden variable $u_k$; and the $u_k$s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map $u_k$ to $x_i$s are well-behaved. After an $O(mathrm{poly}(n))$-time training phase, we achieve $O(n + H_mathrm{S})$ and $O(nalpha(n) + H_mathrm{DT})$ expected running times for sorting and DT, respectively, where $alpha(cdot)$ is the inverse Ackermann function.
Let ${cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The emph{$k$-level} of ${cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${cal L}$ passing below $v$. The complexity (the maximum size) of th
e $k$-level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of $O(ncdot (k+1)^{1/3})$. Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the $k$-level denotes the vertices at distance at most $k$ to a marked cell, the emph{south pole}. We prove an upper bound of $O((k+1)^2)$ on the expected complexity of the $k$-level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great $(d-1)$-spheres on the sphere $mathbb{S}^d$ which are orthogonal to a set of random points on $mathbb{S}^d$. In this model, we prove that the expected complexity of the $k$-level is of order $Theta((k+1)^{d-1})$.
Let $P$ be an $x$-monotone orthogonal polygon with $n$ vertices. We call $P$ a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizontal chord from the left boundary to the right boundary. Two points $p$ a
nd $q$ in $P$ are co-visible if and only if the (axis-parallel) rectangle spanned by $p$ and $q$ completely lies in $P$. In the $r$-visibility graph $G(P)$ of $P$, we connect two vertices of $P$ with an edge if and only if they are co-visible. We consider routing with preprocessing in $G(P)$. We may preprocess $P$ to obtain a label and a routing table for each vertex of $P$. Then, we must be able to route a packet between any two vertices $s$ and $t$ of $P$, where each step may use only the label of the target node $t$, the routing table and neighborhood of the current node, and the packet header. We present a routing scheme for double histograms that sends any data packet along a path whose length is at most twice the (unweighted) shortest path distance between the endpoints. In our scheme, the labels, routing tables, and headers need $O(log n)$ bits. For the case of simple histograms, we obtain a routing scheme with optimal routing paths, $O(log n)$-bit labels, one-bit routing tables, and no headers.
We study self-improving sorting with hidden partitions. Our result is an optimal algorithm which runs in expected time O(H(pi(I)) + n), where I is the given input which contains n elements to be sorted, pi(I) is the output which are the ranks of all
element in I, and H(pi(I)) denotes the entropy of the output.
We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of $n$ vertices and $h$ holes. We introduce a emph{graph of oriented distances} to encode the distance between pairs of poin
ts of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in $min {,O(n^omega), O(n^2 + nh log h + chi^2),}$ time, where $omega<2.373$ denotes the matrix multiplication exponent and $chiin Omega(n)cap O(n^2)$ is the number of edges of the graph of oriented distances. We also provide a faster algorithm for computing the diameter that runs in $O(n^2 log n)$ time.
