International Journal of Computational Geometry & Applications

We present a planar point location structure for a convex subdivision $S$. Given a query sequence of length $m$, the total running time is $O(\mathrm{\text{OPT}}+mloglogn+n)$, where $n$ is the number of vertices in $S$ and $\mathrm{\text{OPT}}$ is the minimum time required by any linear decision tree for answering planar point location queries in $S$ to process the same query sequence. The running time includes the preprocessing time. Therefore, for $m\ge n$, our running time is only worse than the best possible bound by $O(loglogn)$ per query, which is much smaller than the $O(logn)$ query time offered by a worst-case optimal planar point location structure.

We propose an algorithm for finding a $(1+𝜀)$-approximate shortest path through a weighted 3D simplicial complex ${𝒯}$. The weights are integers from the range $[1,W]$ and the vertices have integral coordinates. Let $N$ be the largest vertex coordinate magnitude, and let $n$ be the number of tetrahedra in ${𝒯}$. Let $\rho$ be some arbitrary constant. Let $\kappa$ be the size of the largest connected component of tetrahedra whose aspect ratios exceed $\rho$. There exists a constant $C$ dependent on $\rho$ but independent of ${𝒯}$ such that if $\kappa \le \frac{1}{C}loglogn+O(1)$, the running time of our algorithm is polynomial in $n$, $1/𝜀$ and $log(NW)$. If $\kappa =O(1)$, the running time reduces to $O(n{𝜀}^{-O(1)}{(log(NW))}^{O(1)})$.

An unfolding of a polyhedron is a single connected planar piece without overlap resulting from cutting and flattening the surface of the polyhedron. Even for orthogonal polyhedra, it is known that edge-unfolding, i.e., cuts are performed only along the edges of a polyhedron, is not sufficient to guarantee a successful unfolding in general. However, if additional cuts parallel to polyhedron edges are allowed, it has been shown that every orthogonal polyhedron of genus zero admits a grid-unfolding with quadratic refinement. Using a new unfolding technique developed in this paper, we improve upon the previous result by showing that linear refinement suffices. For 1-layer orthogonal polyhedra of genus $g$, we show a grid-unfolding algorithm using only $2(g-1)$ additional cuts, affirmatively answering an open problem raised in a recent literature. Our approach not only requires fewer cuts but yields much simpler algorithms.

Let $P$ be a set of $n$ labeled points in the plane. The radial system of $P$ describes, for each $p\in P$, the order in which a ray that rotates around $p$ encounters the points in $P\setminus \{p\}$. This notion is related to the order type of $P$, which describes the orientation (clockwise or counterclockwise) of every ordered triple in $P$. Given only the order type, the radial system is uniquely determined and can easily be obtained. The converse, however, is not true. Indeed, let $R$ be the radial system of $P$, and let $T(R)$ be the set of all order types with radial system $R$ (we define $T(R)=\varnothing$ for the case that $R$ is not a valid radial system). Aichholzer et al. (Reconstructing Point Set Order Types from Radial Orderings, in Proc. ISAAC 2014) show that $T(R)$ may contain up to $n-1$ order types. They also provide polynomial-time algorithms to compute $T(R)$ when only $R$ is given.

We describe a new algorithm for finding $T(R)$. The algorithm constructs the convex hulls of all possible point sets with the radial system $R$. After that, orientation queries on point triples can be answered in constant time. A representation of this set of convex hulls can be found in $O(n)$ queries to the radial system, using $O(n)$ additional processing time. This is optimal. Our results also generalize to abstract order types.

The Fréchet distance is a well studied and very popular measure of similarity of two curves. The best known algorithms have quadratic time complexity, which has recently been shown to be optimal assuming the Strong Exponential Time Hypothesis (SETH) [Bringmann, FOCS'14].

To overcome the worst-case quadratic time barrier, restricted classes of curves have been studied that attempt to capture realistic input curves. The most popular such class are $c$-packed curves, for which the Fréchet distance has a $(1+𝜀)$-approximation in time ${𝒪}(cn/𝜀+cnlogn)$ [Driemel et al., DCG'12]. In dimension $d\ge 5$ this cannot be improved to ${𝒪}({(cn/\sqrt{𝜀})}^{1-\delta })$ for any $\delta >0$ unless SETH fails [Bringmann, FOCS'14].

In this paper, exploiting properties that prevent stronger lower bounds, we present an improved algorithm with time complexity ${𝒪}(cn{log}^2(1/𝜀)/\sqrt{𝜀}+cnlogn)$. This improves upon the algorithm by Driemel et al. for any $𝜀\ll 1/logn$. Moreover, our algorithm's dependence on $c$, $n$ and $𝜀$ is optimal in high dimensions apart from lower order factors, unless SETH fails. Our main new ingredients are as follows: For filling the classical free-space diagram we project short subcurves onto a line, which yields one-dimensional separated curves with roughly the same pairwise distances between vertices. Then we tackle this special case in near-linear time by carefully extending a greedy algorithm for the Fréchet distance of one-dimensional separated curves.

A greedily routable region (GRR) is a closed subset of ${ℝ}^2$, in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes.

We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected.