International Journal of Computational Geometry & Applications

In 1985 Hopcroft, Joseph and Whitesides showed it is NP-complete to decide whether a carpenter’s ruler with segments of given positive lengths can be folded into an interval of at most a given length, such that the folded hinges alternate between 180 degrees clockwise and 180 degrees counter-clockwise. At the open-problem session of 33rd Canadian Conference on Computational Geometry (CCCG ’21), O’Rourke proposed a natural variation of this problem called ruler wrapping, in which all folded hinges must be folded the same way. In this paper we show O’Rourke’s variation has a linear-time solution.

Given a set $C$ of points and a horizontal line $L$ in the plane and a set $F$ of points on $L$, we want to find a set of disks such that (1) each disk has the center at a point in $F$ (but with arbitrary radius), (2) each point in $C$ is covered by at least one disk, and (3) the cost of the set of disks is minimized. Here the (transmission) cost of a disk with radius $r$ is $r^{\alpha }$, where $\alpha$ is a positive constant depending on the power consumption model, and the cost of a set of disk is the sum of the cost of disks in the set.

In this paper we first give an algorithm based on dynamic programming method to solve the problem in $L_1$ metric. A naive dynamic programming algorithm runs in $O(|C{|}^3|F{|}^2)$ time. We design an algorithm which runs in $O(|C\left|\right|F{|}^2+\left|C\right|log\left|C\right|)$ time.

Then we design another algorithm to solve the problem in $L_1$ metric based on a reduction to a shortest path problem in a directed acyclic graph. The running time of the algorithm is $O(|C{|}^2+\left|C\right|\left|F\right|)$.

Chvátal and Klincsek (1980) gave an $O(n^3)$-time algorithm for the problem of finding a maximum-cardinality convex subset of an arbitrary given set $P$ of $n$ points in the plane. This paper examines a generalization of the problem, the Bottleneck Convex Subsets problem: given a set $P$ of $n$ points in the plane and a positive integer $k$, select $k$ pairwise disjoint convex subsets of $P$ such that the cardinality of the smallest subset is maximized. Equivalently, a solution maximizes the cardinality of $k$ mutually disjoint convex subsets of $P$ of equal cardinality. We give an algorithm that solves the problem exactly, with running time polynomial in $n$ when $k$ is fixed. We then show the problem to be NP-hard when $k$ is an arbitrary input parameter, even for points in general position. Finally, we give a fixed-parameter tractable algorithm parameterized in terms of the number of points strictly interior to the convex hull.

Orthogonal range search is ubiquitous nowadays, with natural applications in databases, data mining, and text indexing. Very recently, yet another application was discovered, which is to maintain a DFS forest in a dynamic graph. In this paper, we want to extend the above recent study, by applying orthogonal range search to efficient maintenance of a BFS-like forest, called no-back-edge-traversal (NBET) forest, which refers to a spanning forest obtained from a traversal that does not create any back edge. The study of such a problem is motivated by the fact that NBET forest can be used as a strong certificate of 2-connectivity of an undirected graph, which is more general than a spanning forest obtained from a scan-first search traversal.