International Journal of Computational Geometry & Applications

We study the problem of folding a polyomino $P$ into a polycube $Q$, allowing faces of $Q$ to be covered multiple times. First, we define a variety of folding models according to whether the folds (a) must be along grid lines of $P$ or can divide squares in half (diagonally and/or orthogonally), (b) must be mountain or can be both mountain and valley, (c) can remain flat (forming an angle of $180^{\circ }$), and (d) must lie on just the polycube surface or can have interior faces as well. Second, we give all the inclusion relations among all models that fold on the grid lines of $P$. Third, we characterize all polyominoes that can fold into a unit cube, in some models. Fourth, we give a linear-time dynamic programming algorithm to fold a tree-shaped polyomino into a constant-size polycube, in some models. Finally, we consider the triangular version of the problem, characterizing which polyiamonds fold into a regular tetrahedron.

In this paper, we study the problem of designing robust algorithms for computing the minimum spanning tree, the nearest neighbor graph, and the relative neighborhood graph of a set of points in the plane, under the Euclidean metric. We use the term “robust” to denote an algorithm that can properly handle degenerate configurations of the input (such as co-circularities and collinearities) and that is not affected by errors in the flow of control due to round-off approximations. Existing asymptotically optimal algorithms that compute such graphs are either suboptimal in terms of the arithmetic precision required for the implementation, or cannot handle degeneracies, or are based on complex data structures.

We present a unified approach to the robust computation of the above graphs. The approach is a variant of the general region approach for the computation of proximity graphs based on Yao graphs, first introduced in Ref. 43 (A. C.-C. Yao, On constructing minimum spanning trees in $k$-dimensional spaces and related problems, SIAM J. Comput. 11(4) (1982) 721–736). We show that a sparse supergraph of these geometric graphs can be computed in asymptotically optimal time and space, and requiring only double precision arithmetic, which is proved to be optimal. The arithmetic complexity of the approach is measured by using the notion of degree, introduced in Ref. 31 (G. Liotta, F. P. Preparata and R. Tamassia, Robust proximity queries: An illustration of degree-driven algorithm design, SIAM J. Comput. 28(3) (1998) 864–889) and Ref. 3 (J. D. Boissonnat and F. P. Preparata, Robust plane sweep for intersecting segments, SIAM J. Comput. 29(5) (2000) 1401–1421).

As a side effect of our results, we solve a question left open by Katajainen²⁷ (J. Katajainen, The region approach for computing relative neighborhood graphs in the $L_p$ metric, Computing 40 (1987) 147–161) about the existence of a subquadratic algorithm, based on the region approach, that computes the relative neighborhood graph of a set of points $S$ in the plane under the $L_2$ metric.

Let $X_n$ be a planar Poisson point process of intensity $n$. We give a new proof that the expected length of the Voronoi path between $(0,0)$ and $(1,0)$ in the Delaunay triangulation associated with $X_n$ is $\frac{4}{\pi }\simeq 1.27$ when $n$ goes to infinity; and we also prove that the variance of this length is $\mathrm{\Theta }(1/\sqrt{n})$. We investigate the length of possible shortcuts in this path, and define a shortened Voronoi path whose expected length can be expressed as an integral that is numerically evaluated to $\simeq 1.16$. The shortened Voronoi path has the property to be locally defined; and is shorter than the previously known locally defined paths in Delaunay triangulation such as the upper path whose expected length is $35/3{\pi }^2\simeq 1.18$.

In this paper, we consider the rectilinear one-center problem on uncertain points in the plane. In this problem, we are given a set ${𝒫}$ of $n$ (weighted) uncertain points in the plane and each uncertain point has $m$ possible locations each associated with a probability for the point appearing at that location. The goal is to find a point $q^{\ast }$ in the plane which minimizes the maximum expected rectilinear distance from $q^{\ast }$ to all uncertain points of ${𝒫}$, and $q^{\ast }$ is called a rectilinear center. We present an algorithm that solves the problem in $O(mn)$ time. Since the input size of the problem is $\mathrm{\Theta }(mn)$, our algorithm is optimal.

A conflict-free$k$-coloring of a graph $G=(V,E)$ assigns one of $k$ different colors to some of the vertices such that, for every vertex $v$, there is a color that is assigned to exactly one vertex among $v$ and $v$’s neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well studied in graph theory. Here we study the conflict-free coloring of geometric intersection graphs. We demonstrate that the intersection graph of $n$ geometric objects without fatness properties and size restrictions may have conflict-free chromatic number in $\mathrm{\Omega }(logn/loglogn)$ and in $\mathrm{\Omega }(\sqrt{logn})$ for disks or squares of different sizes; it is known for general graphs that the worst case is in $\mathrm{\Theta }({log}^{2}n)$. For unit-disk intersection graphs, we prove that it is NP-complete to decide the existence of a conflict-free coloring with one color; we also show that six colors always suffice, using an algorithm that colors unit disk graphs of restricted height with two colors. We conjecture that four colors are sufficient, which we prove for unit squares instead of unit disks. For interval graphs, we establish a tight worst-case bound of two.