International Journal of Computational Geometry & Applications

We present tight bounds on the spanning ratio of a large family of ordered $\theta$-graphs. A $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta =2\pi /m$. An ordered $\theta$-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone. We show that for any integer $k\ge 1$, ordered $\theta$-graphs with $4k+4$ cones have a tight spanning ratio of $1+2sin(\theta /2)/(cos(\theta /2)-sin(\theta /2))$. We also show that for any integer $k\ge 2$, ordered $\theta$-graphs with $4k+2$ cones have a tight spanning ratio of $1/(1-2sin(\theta /2))$. We provide lower bounds for ordered $\theta$-graphs with $4k+3$ and $4k+5$ cones. For ordered $\theta$-graphs with $4k+2$ and $4k+5$ cones these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered $\theta$-graphs have worse spanning ratios than unordered $\theta$-graphs. Finally, we show that, unlike their unordered counterparts, the ordered $\theta$-graphs with 4, 5, and 6 cones are not spanners.

Let ${𝒮}=\{(s_1,{\pi }_1),(s_2,{\pi }_2),\dots ,(s_n,{\pi }_n)\}$ be a set of stochastic sites, where each site is a tuple $(s_i,{\pi }_i)$ consisting of a point $s_i$ in $d$-dimensional space and a probability ${\pi }_i$ of existence. Given a query point $q$, we define its most likely nearest neighbor (LNN) as the site with the largest probability of being $q$’s nearest neighbor. The Most Likely Voronoi Diagram (LVD) of ${𝒮}$ is a partition of the space into regions with the same LNN. We investigate the complexity of LVD in one dimension and show that it can have size $\mathrm{\Omega }(n^2)$ in the worst-case. We then show that under non-adversarial conditions, the size of the $1$-dimensional LVD is significantly smaller: (1) $\mathrm{\Theta }(kn)$ if the input has only $k$ distinct probability values, (2) $O(nlogn)$ on average, and (3) $O(n\sqrt{n})$ under smoothed analysis. We also describe a framework for LNN search using Pareto sets, which gives a linear-space data structure and sub-linear query time in 1D for average and smoothed analysis models as well as the worst-case with a bounded number of distinct probabilities. The Pareto-set framework is also applicable to multi-dimensional LNN search via reduction to a sequence of nearest neighbor and spherical range queries.

We consider the problem of reconstructing the combinatorial structure of a set of $n\ge 5$ points in the plane given partial information on the relative position of the points. This partial information consists of the radial ordering, for each of the $n$ points, of the $n-1$ other points around it. We show that this information is sufficient to reconstruct the chirotope, or labeled order type, of the point set, provided its convex hull has size at least four. Otherwise, we show that there can be as many as $n-1$ distinct chirotopes that are compatible with the partial information, and this bound is tight. Our proofs yield polynomial-time reconstruction algorithms. These results provide additional theoretical insights on previously studied problems related to robot navigation and visibility-based reconstruction.

The (weighted) $k$-median, $k$-means, and $k$-center problems in the plane are known to be NP-hard. In this paper, we study these problems with an additional constraint that requires the sought $k$ facilities to be on a given line. We present efficient algorithms for various distance measures such as $L_1,L_2,L_{\infty }$. We assume that all $n$ weighted points are given sorted by their projections on the given line. For $k$-median, our algorithms for $L_1$ and $L_{\infty }$ metrics run in $O(min\{nk,n\sqrt{klogn}logn,n{2}^{O(\sqrt{logkloglogn})}logn\})$ time and $O(min\{nklogn,n\sqrt{klogn}{log}^{2}n,n{2}^{O(\sqrt{logkloglogn})}{log}^{2}n\})$ time, respectively. For $k$-means, which is defined only on the squared $L_2$ distance, we give an $O(min\{nk,n\sqrt{klogn},n{2}^{O(\sqrt{logkloglogn})}\})$ time algorithm. For $k$-center, our algorithms run in $O(nlogn)$ time for all three metrics, and in $O(n)$ time for the unweighted version under $L_1$ and $L_{\infty }$ metrics. While our results for the $k$-center problem are optimal, the results for the $k$-median problem almost match the best algorithms for the corresponding one-dimensional problems.

We introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist.

Using our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings.