International Journal of Computational Geometry & Applications

We consider a random variable expressed as the Euclidean distance between an arbitrary point and a random variable uniformly distributed in a closed and bounded set of a three-dimensional Euclidean space. Four cases are considered for this set: a union of disjoint disks, a union of disjoint balls, a union of disjoint line segments, and the boundary of a polyhedron. In the first three cases, we provide closed-form expressions of the cumulative distribution function and the density. In the last case, we propose two algorithms with complexity $O(nlnn)$, $n$ being the number of edges of the polyhedron, that computes exactly the cumulative distribution function. An application of these results to probabilistic seismic hazard analysis and extensions are discussed. Finally, we present an open source library, available at https://github.com/vguigues/Areas_Library, that implements the algorithms presented in this paper.

Given a set $S$ of $n$ points, a weight function $w$ to associate a non-negative weight to each point in $S$, a positive integer $k\ge 1$, and a real number $𝜖>0$, we present algorithms for computing a spanner network $G(S,E)$ for the metric space $(S,d_w)$ induced by the weighted points in $S$. The weighted distance function $d_w$ on the set $S$ of points is defined as follows: for any $p,q\in S$, $d_w(p,q)$ is equal to $w(p)+d_{\pi }(p,q)+w(q)$ if $p\ne q$, otherwise, $d_w(p,q)$ is $0$. Here, $d_{\pi }(p,q)$ is the Euclidean distance between $p$ and $q$ if points in $S$ are in ${ℝ}^d$, otherwise, it is the geodesic (Euclidean) distance between $p$ and $q$. The following are our results: (1) When the weighted points in $S$ are located in ${ℝ}^d$, we compute a $k$-vertex fault-tolerant $(4+𝜖)$-spanner network of size $O(\frac{kn}{{𝜖}^2})$. (2) When the weighted points in $S$ are located in the relative interior of the free space of a polygonal domain ${𝒫}$, we detail an algorithm to compute a $k$-vertex fault-tolerant $(4+𝜖)$-spanner network with $O(\frac{kn\sqrt{h+1}}{{𝜖}^2}lgn)$ edges. Here, $h$ is the number of simple polygonal holes in ${𝒫}$. (3) When the weighted points in $S$ are located on a polyhedral terrain ${𝒯}$, we propose an algorithm to compute a $k$-vertex fault-tolerant $(4+𝜖)$-spanner network, and the number of edges in this network is $O(\frac{kn}{{𝜖}^2}lgn)$.

Robust optimization problems have attracted considerable attention in recent years. In this paper, we focus on two fundamental robust optimization problems: SVM with outliers and $k$-center clustering with outliers. The key obstacle is that the outliers can be located arbitrarily in the space (e.g., by an attacker), and thus they are actually quite challenging combinatorial optimization problems. Their computational complexities can be very high especially in high dimensional spaces. The Johnson–Lindenstrauss $($JL $)$ Transform is a popular random projection method for dimension reduction. Though the JL transform has been widely studied in the past decades, its effectiveness for dealing with high-dimensional optimizations with outliers has never been investigated before (to the best of our knowledge). Based on some novel insights from the geometry, we prove that the complexities of these two problems can be significantly reduced through the JL transform. Moreover, we prove that the solution in the dimensionality-reduced space can be efficiently recovered in the original ${ℝ}^d$ space while the quality is still preserved. To study its performance in practice, we compare different JL transform methods with several other well known dimension reduction methods in our experiments.