International Journal of Computational Geometry & Applications

Piecewise-linear terrains (“roofs”) over simple polygons were first studied by Aichholzer et al. (J. UCS 1995) in their work on straight skeletons of polygons. We show how to construct a roof over the polygonal footprint of a building that has minimum or maximum volume among all roofs that drain water. Our algorithm for computing such a roof extends the standard plane-sweep approach known from the theory of straight skeletons by additional events. For both types of roofs our algorithm runs in ${𝒪}(n^3\mathrm{\text{log}}n)$ time for a simple polygon with $n$ vertices.

We study unique coverage problems with rectangle and half-strip regions, motivated by wireless networks in the context of coverage using directional antennae without interference. Given a set $C$ of points (clients) and a set $A$ of directional antennae in the plane, the goal is to assign a direction to each directional antenna in $A$, such that the number of clients in $C$ that are uniquely covered by the directional antennae is maximized. A client is covered uniquely if it is covered by exactly one antenna. We consider two types of rectangular regions representing half-strip directional antennae: unbounded half-strips and half-strips bounded by a range $r$ (i.e., $3$-sided rectangular regions and rectangular regions). The directional antennae can be directed up or down. We present two polynomial time algorithms: an optimal solution for the problem with the $3$-sided rectangular regions, and a constant factor approximation for the rectangular regions.

Helly’s theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If $S$ is a set of $n$ points in ${ℝ}^d$, we say that $S$ is $(k,G)$-clusterable if it can be partitioned into $k$ clusters (subsets) such that each cluster can be contained in a translated copy of a geometric object $G$. In this paper, as an application of Helly’s theorem, by taking a constant size sample from $S$, we present a testing algorithm for $(k,G)$-clustering, i.e., to distinguish between the following two cases: when $S$ is $(k,G)$-clusterable, and when it is $𝜖$-far from being $(k,G)$-clusterable. A set $S$ is $𝜖$-far $(0<𝜖\le 1)$ from being $(k,G)$-clusterable if at least $𝜖n$ points need to be removed from $S$ in order to make it $(k,G)$-clusterable. We solve this problem when $k=1$, and $G$ is a symmetric convex object. For $k>1$, we solve a weaker version of this problem. Finally, as an application of our testing result, in the case of clustering with outliers, we show that with high probability one can find the approximate clusters by querying only a constant size sample.

Given a set $P=\{p_1,\dots ,p_n\}$ of points and a point $q$ in the plane, we define a function $\psi (q)$ that provides a combinatorial characterization of the multiset of values $\{|P\cap H_i|\}$, where for each $i\in \{1,\dots ,n\}$, $H_i$ is the open half-plane determined by $q$ and $p_i$. We introduce two new natural measures of depth, perihedral depth and eutomic depth, and we show how to express these and the well-known simplicial and Tukey depths concisely in terms of $\psi (q)$. The perihedral and eutomic depths of $q$ with respect to $P$ correspond respectively to the number of subsets of $P$ whose convex hull contains $q$, and the number of combinatorially distinct bisections of $P$ determined by a line through $q$. We present algorithms to compute the depth of an arbitrary query point in $O(n\mathrm{\text{log}}n)$ time and medians (deepest points) with respect to these depth measures in $O(n^4)$ and $O(n^{8/3})$ time respectively. For comparison, these results match or slightly improve on the corresponding best-known running times for simplicial depth, whose definition involves similar combinatorial complexity.