For a set P of n points in the unit ball b ⊆ R
d
,
consider the problem of finding a small subset
T ⊆ P such that its convexhull εapproximates
the convexhull of the original set. Specifically, the
Hausdorff distance between the convex hull of T
and the convex hull of P should be at most ε. We
present an efficient algorithm to compute such an
ε
′
approximation of size kalg, where ε
′
is a function
of ε, and kalg is a function of the minimum size kopt
of such an εapproximation. Surprisingly, there is
no dependence on the dimension d in either of the
bounds. Furthermore, every point of P can be ε
approximated by a convexcombination of points
of T that is O(1/ε2
)sparse.
Our result can be viewed as a method for
sparse, convex autoencoding: approximately representing
the data in a compact way using sparse
combinations of a small subset T of the original
data. The new algorithm can be kernelized, and
it preserves sparsity in the original input.
more »
« less
Computing the Caratheodory Number of a Point
Caratheodory’s theorem says that any point in the convex hull of a set $P$ in $R^d$ is in the convex hull of a subset $P'$ of $P$ such that $P' \le d + 1$. For some sets P, the upper bound d + 1 can be improved. The best upper bound for P is known as the Caratheodory number [2, 15, 17]. In this paper, we study a computational problem of finding the smallest set $P'$ for a given set $P$ and a point $p$. We call the size of this set $P'$, the Caratheodory number of a point p or CNP. We show that the problem of deciding the Caratheodory number
of a point is NPhard. Furthermore, we show that the problem is kLDThard. We present two algorithms for computing a smallest set $P'$, if CNP= 2,3.
Bárány [1] generalized Caratheodory’s theorem by using d+1 sets (colored sets) such that their convex hulls intersect. We introduce a Colorful Caratheodory number of a point or CCNP which can be smaller than d+1. Then we extend our results for CNP to CCNP.
more »
« less
 Award ID(s):
 1718994
 NSFPAR ID:
 10196676
 Date Published:
 Journal Name:
 Canadian Conference on Computational Geometry
 Page Range / eLocation ID:
 192198
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Let P be a set n points in a ddimensional space. Tverberg theorem says that, if n is at least (k − 1)(d + 1), then P can be par titioned into k sets whose convex hulls intersect. Partitions with this property are called Tverberg partitions. A partition has tolerance t if the partition remains a Tverberg partition after removal of any set of t points from P. A tolerant Tverberg partition exists in any dimensions provided that n is sufficiently large. Let N(d,k,t) be the smallest value of n such that tolerant Tverberg partitions exist for any set of n points in R d . Only few exact values of N(d,k,t) are known. In this paper, we study the problem of finding Radon partitions (Tver berg partitions for k = 2) for a given set of points. We develop several algorithms and found new lower bounds for N(d,2,t).more » « less

In this article, we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. An uncertain curve is a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NPhard for the Fréchet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound (discrete [ 5 ] and continuous) Fréchet distance can be computed in polynomial time in some models. Furthermore, we show that computing the expected (discrete and continuous) Fréchet distance is #Phard in some models. On the positive side, we present an FPTAS in constant dimension for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We also show a nearlineartime 3approximation for the decision problem on roughly δseparated convex regions. Finally, we study the setting with Sakoe–Chiba time bands, where we restrict the alignment between the curves, and give polynomialtime algorithms for the upper bound and expected discrete and continuous Fréchet distance for uncertainty modelled as point sets.more » « less

Bojanczyk, Mikolaj ; Chekuri, Chandra (Ed.)Given a point set P in the plane, we seek a subset Q ⊆ P, whose convex hull gives a smaller and thus simpler representation of the convex hull of P. Specifically, let cost(Q,P) denote the Hausdorff distance between the convex hulls CH(Q) and CH(P). Then given a value ε > 0 we seek the smallest subset Q ⊆ P such that cost(Q,P) ≤ ε. We also consider the dual version, where given an integer k, we seek the subset Q ⊆ P which minimizes cost(Q,P), such that Q ≤ k. For these problems, when P is in convex position, we respectively give an O(n log²n) time algorithm and an O(n log³n) time algorithm, where the latter running time holds with high probability. When there is no restriction on P, we show the problem can be reduced to APSP in an unweighted directed graph, yielding an O(n^2.5302) time algorithm when minimizing k and an O(min{n^2.5302, kn^2.376}) time algorithm when minimizing ε, using prior results for APSP. Finally, we show our near linear algorithms for convex position give 2approximations for the general case.more » « less

We present new results on a number of fundamental problems about dynamic geometric data structures: 1) We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1center of a 2D point set, (v) the number of maximal (i.e., skyline) points in a 3D point set. The update times are near n^{11/12} for (i) and (ii), n^{7/8} for (iii) and (iv), and n^{2/3} for (v). Previously, sublinear bounds were known only for restricted "semionline" settings [Chan, SODA 2002]. 2) We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is O(log^2n), and the amortized update time is O(log^4n) instead of O(log^5n) [Chan, SODA 2006; Kaplan et al., SODA 2017]. 3) We also improve previous fully dynamic data structures for maintaining the bichromatic closest pair between two 2D point sets and the diameter of a 2D point set. The amortized update time is O(log^4n) instead of O(log^7n) [Eppstein 1995; Chan, SODA 2006; Kaplan et al., SODA 2017].more » « less