Few Cuts Meet Many Point Sets Har-Peled, Sariel; Jones, Mitchell
Algorithmica,
04/2023, Letnik:
85, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We study the problem of how to split many point sets in
R
d
into smaller parts using a few (shared) splitting hyperplanes. This problem is related to the classical Ham-Sandwich Theorem. We provide a ...logarithmic approximation to the optimal solution using the greedy algorithm for submodular optimization.
Given a set of
n
points in the plane, and a parameter
k
, we consider the problem of computing the minimum (perimeter or area) axis-aligned rectangle enclosing
k
points. We present the first near ...quadratic time algorithm for this problem, improving over the previous near-
O
(
n
5
/
2
)
-time algorithm by Kaplan et al. (25th European Symposium on Algorithms. Leibniz Int Proc Inform, vol. 87, # 52. Leibniz-Zent Inform, Wadern, 2017). We provide an almost matching conditional lower bound, under the assumption that
(
min
,
+
)
-convolution cannot be solved in truly subquadratic time. Furthermore, we present a new reduction (for both perimeter and area) that can make the time bound sensitive to
k
, giving near
O
(
n
k
)
time. We also present a near linear time
(
1
+
ε
)
-approximation algorithm to the minimum area of the optimal rectangle containing
k
points. In addition, we study related problems including the 3-sided, arbitrarily oriented, weighted, and subset sum versions of the problem.
A Spanner for the Day After Buchin, Kevin; Har-Peled, Sariel; Oláh, Dániel
Discrete & computational geometry,
12/2020, Letnik:
64, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We show how to construct a
(
1
+
ε
)
-spanner over a set
P
of
n
points in
R
d
that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters
ϑ
,
ε
∈
(
0
,
1
)
, the ...computed spanner
G
has
O
(
ε
-
O
(
d
)
ϑ
-
6
n
(
log
log
n
)
6
log
n
)
edges. Furthermore, for
any
k
, and
any
deleted set
B
⊆
P
of
k
points, the residual graph
G
\
B
is a
(
1
+
ε
)
-spanner for all the points of
P
except for
(
1
+
ϑ
)
k
of them. No previous constructions, beyond the trivial clique with
O
(
n
2
)
edges, were known with this resilience property (i.e., only a tiny additional fraction of vertices,
ϑ
|
B
|
, lose their distance preserving connectivity). Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black-box fashion.
Consider a set
P
⊆
R
d
of
n
points, and a convex body
C
provided via a separation oracle. The task at hand is to decide for each point of
P
if it is in
C
using the fewest number of oracle queries. We ...show that one can solve this problem in two and three dimensions using
queries, where
is the size of the largest subset of points of
P
in convex position. In 2D, we provide an algorithm that efficiently generates these adaptive queries. Furthermore, we show that in two dimensions one can solve this problem using
oracle queries, where
is a lower bound on the minimum number of queries that any algorithm for this specific instance requires. Finally, we consider other variations on the problem, such as using the fewest number of queries to decide if
C
contains all points of
P
. As an application of the above, we show that the discrete geometric median of a point set
P
in
R
2
can be computed in
expected time.
This work is motivated by several basic problems and techniques that rely on space decomposition of arrangements of hyperplanes in high-dimensional spaces, most notably Meiser’s 1993 algorithm ...(Meiser in Inf Comput 106(2):286–303, 1993) for point location in such arrangements. A standard approach to these problems is via random sampling, in which one draws a random sample of the hyperplanes, constructs a suitable decomposition of its arrangement, and recurses within each cell of the decomposition with the subset of hyperplanes that cross the cell. The efficiency of the resulting algorithm depends on the quality of the sample, which is controlled by various parameters. One of these parameters is the classical
VC-dimension
, and its associated
primal shatter dimension
, of a suitably defined corresponding range space. Another parameter, which we refer to here as the
combinatorial dimension
, is the maximum number of hyperplanes that are needed to define a cell that can arise in the decomposition of some sample of the input hyperplanes; this parameter arises in Clarkson’s (and later Clarkson and Shor’s) random sampling technique. We re-examine these parameters for the two main space decomposition techniques—
bottom-vertex triangulation
, and
vertical decomposition
, including their explicit dependence on the dimension
d
, and discover several unexpected phenomena, which show that, in both techniques, there are large gaps between the VC-dimension (and primal shatter dimension), and the combinatorial dimension. Our main application is to point location in an arrangement of
n
hyperplanes is
R
d
, in which we show that the query cost in Meiser’s algorithm can be improved if one uses vertical decomposition instead of bottom-vertex triangulation, at the cost of some increase in the preprocessing cost and storage (which seem to be stated incorrectly, and are not worked out, in Meiser’s work). Our improved bounds rely on establishing several new structural properties and improved complexity bounds for vertical decomposition, which are of independent interest, and which we expect to find additional applications.
We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local-search ...algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, which leads to a constant-factor approximation.
Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.
Let
L
be a set of
n
lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement
A
(
L
)
of maximum level, where the ...level of a vertex
v
is the number of lines of
L
that pass strictly below
v
. The problem, posed in Exercise 8.13 in de Berg et al. (Computational Geometry. Algorithms and Applications. Springer, Berlin (2008)), appears to be much harder than it seems at first sight, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of
L
are distinct, and distinguish between two cases, depending on whether or not the upper envelope of
L
contains a bounded edge. In the former case, we show that the number of lines of
L
that pass
above
any maximum level vertex
v
0
is only
O
(
log
n
)
. In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal
O
(
n
log
n
)
time. We then consider the case where the lines of
L
are not necessarily distinct. This setup is more challenging, and for this case we present an algorithm that computes all the maximum-level vertices in time
O
(
n
4
/
3
log
3
n
)
. Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the
weighted
k
-
level
in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is
O
(
n
4
/
3
)
, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.
A graph drawn in the plane with
n
vertices is
k
-fan-crossing free
for
k
⩾
2
if there are no
k
+
1
edges
g
,
e
1
,
…
,
e
k
, such that
e
1
,
e
2
,
…
,
e
k
have a common endpoint and
g
crosses all
e
...i
. We prove a tight bound of
4
n
-
8
on the maximum number of edges of a
2
-fan-crossing free graph, and a tight
4
n
-
9
bound for a straight-edge drawing. For
k
⩾
3
, we prove an upper bound of
3
(
k
-
1
)
(
n
-
2
)
edges. We also discuss generalizations to monotone graph properties.
The similarity of two polygonal curves can be measured using the Frechet distance. We introduce the notion of a more robust Frechet distance, where one is allowed to shortcut between vertices of one ...of the curves. This is a natural approach for handling noise, in particular batched outliers. We compute a $(3+\varepsilon)$-approximation to the minimum Frechet distance over all possible such shortcuts, in near linear time, if the curve is $c$-packed and the number of shortcuts is either small or unbounded. To facilitate the new algorithm we develop several new tools: (a) a data structure for preprocessing a curve (not necessarily $c$-packed) that supports $(1+\varepsilon)$-approximate Frechet distance queries between a subcurve (of the original curve) and a line segment; (b) a near linear time algorithm that computes a permutation of the vertices of a curve, such that any prefix of $2k-1$ vertices of this permutation forms an optimal approximation (up to a constant factor) to the original curve compared to any polygonal curve with $k$ vertices, for any $k > 0$; and (c) a data structure for preprocessing a curve that supports approximate Frechet distance queries between a subcurve and query polygonal curve. The query time depends quadratically on the complexity of the query curve and only (roughly) logarithmically on the complexity of the original curve. To our knowledge, these are the first data structures to support these kind of queries efficiently. PUBLICATION ABSTRACT
We present a (1+ε)-approximation algorithm with quasi-polynomial running time for computing a maximum weight independent set of polygons from a given set of polygons in the plane. Contrasting this, ...the best-known polynomial time algorithm for the problem has an approximation ratio of
n
ε
. Surprisingly, we can extend the algorithm to the problem of computing the maximum cardinality subset of the given set of polygons whose intersection graph fulfills some sparsity condition. For example, we show that one can approximate the maximum subset of polygons such that the intersection graph of the subset is planar or does not contain a cycle of length 4 (i.e.,
K
2,2
). Our algorithm relies on a recursive partitioning scheme, whose backbone is the existence of balanced cuts with small complexity that intersect polygons from the optimal solution of a small total weight.
For the case of large axis-parallel rectangles, we provide a
polynomial
time (1 + ε)-approximation for the maximum weight independent set. Specifically, we consider the problem where each rectangle has one edge whose length is at least a constant fraction of the length of the corresponding edge of the bounding box of all the input elements. This is now the most general case for which a PTAS is known, and it requires a new and involved partitioning scheme, which should be of independent interest.
PDF
