Let L be a set of n axis-parallel lines in R3. We are are interested in partitions of R3 by a set H of three planes such that each open cell in the arrangement A(H) is intersected by as few lines from L as possible. We study such partitions in three settings, depending on the type of splitting planes that we allow. We obtain the following results. * There are sets L of n axis-parallel lines such that, for any set H of three splitting planes, there is an open cell in A(H) that intersects at least ⌊n/3⌋ - 1 ≈ n/3 lines. * If we require the splitting planes to be axis-parallel, then there are sets L of n axis-parallel lines such that, for any set H of three splitting planes, there is an open cell in A(H) that intersects at least (3/2) ⌊n/3⌋ - 1 ≈ (1/3 + 1/24) n lines. Furthermore, for any set L of n axis-parallel lines, there exists a set H of three axis-parallel splitting planes such that each open cell in A(H) intersects at most (7/18) n = (1/3 + 1/18) n lines. * For any set L of n axis-parallel lines, there exists a set H of three axis-parallel and mutually orthogonal splitting planes, such that each open cell in A(H) intersects at most ⌈5/12 n⌉ ≈ (1/3 + 1/12) n lines. more »« less
Agarwal, Pankaj K; Ezra, Esther
(, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
Chambers, Erin W; Gudmundsson, Joachim
(Ed.)
Let ℬ be a set of n unit balls in ℝ³. We present a linear-size data structure for storing ℬ that can determine in O^*(n^{1/2}) time whether a query line intersects any ball of ℬ and report all k such balls in additional O(k) time. The data structure can be constructed in O(n log n) time. (The O^*(⋅) notation hides subpolynomial factors, e.g., of the form O(n^ε), for arbitrarily small ε > 0, and their coefficients which depend on ε.) We also consider the dual problem: Let ℒ be a set of n lines in ℝ³. We preprocess ℒ, in O^*(n²) time, into a data structure of size O^*(n²) that can determine in O^*(1) time whether a query unit ball intersects any line of ℒ, or report all k such lines in additional O(k) time.
Bereg Sergey, Haghpanah Mohammadreza
(, Lecture notes in computer science)
Let P be a set n points in a d-dimensional 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).
Aronov, Boris; Basit, Abdul; Ramesh, Indu; Tasinato, Gianluca; Wagner, Uli
(, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
Mulzer, Wolfgang; Phillips, Jeff M
(Ed.)
An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).
Abstract We generalize the Guth–Katz joints theorem from lines to varieties. A special case says that N planes (2-flats) in 6 dimensions (over any field) have $$O(N^{3/2})$$ O ( N 3 / 2 ) joints, where a joint is a point contained in a triple of these planes not all lying in some hyperplane. More generally, we prove the same bound when the set of N planes is replaced by a set of 2-dimensional algebraic varieties of total degree N , and a joint is a point that is regular for three varieties whose tangent planes at that point are not all contained in some hyperplane. Our most general result gives upper bounds, tight up to constant factors, for joints with multiplicities for several sets of varieties of arbitrary dimensions (known as Carbery’s conjecture). Our main innovation is a new way to extend the polynomial method to higher dimensional objects, relating the degree of a polynomial and its orders of vanishing on a given set of points on a variety.
Singer, Noah; Sudan, Madhu
(, ACM Transactions on Computation Theory)
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in ℝ d that is covered by constant-sized sets of parallel hyperplanes, there exists an affine subspace that accounts for a large (i.e., 2 –polylog( d ) ) fraction of the incidences, in the sense of containing a large fraction of the points and being contained in a large fraction of the hyperplanes. In other words, the point-hyperplane incidence graph for such configurations has a large complete bipartite subgraph. Alternatively, our conjecture may be interpreted linear-algebraically as follows: Any rank- d matrix containing at most O (1) distinct entries in each column contains a submatrix of fractional size 2 –polylog( d ) , in which each column is constant. We prove that our conjecture is equivalent to the log-rank conjecture; the crucial ingredient of this proof is a reduction from bounds for parallel k -partitions to bounds for parallel ( k -1)-partitions. We also introduce an (apparent) strengthening of the conjecture, which relaxes the requirements that the sets of hyperplanes be parallel. Motivated by the connections above, we revisit well-studied questions in point-hyperplane incidence geometry without structural assumptions (i.e., the existence of partitions). We give an elementary argument for the existence of complete bipartite subgraphs of density Ω (ε 2 d / d ) in any d -dimensional configuration with incidence density ε, qualitatively matching previous results proved using sophisticated geometric techniques. We also improve an upper-bound construction of Apfelbaum and Sharir [ 2 ], yielding a configuration whose complete bipartite subgraphs are exponentially small and whose incidence density is Ω (1/√ d ). Finally, we discuss various constructions (due to others) of products of Boolean matrices which yield configurations with incidence density Ω (1) and complete bipartite subgraph density 2 -Ω (√ d ) , and pose several questions for this special case in the alternative language of extremal set combinatorics. Our framework and results may help shed light on the difficulty of improving Lovett’s Õ(√ rank( f )) bound [ 20 ] for the log-rank conjecture. In particular, any improvement on this bound would imply the first complete bipartite subgraph size bounds for parallel 3-partitioned configurations which beat our generic bounds for unstructured configurations.
Aronov, Boris, Basit, Abdul, de Berg, Mark, and Gudmundsson, Joachim. Computing in Geometry and Topology. Retrieved from https://par.nsf.gov/biblio/10496292. Computing in Geometry and Topology 2. Web. doi:10.57717/cgt.v2i1.14.
Aronov, Boris, Basit, Abdul, de Berg, Mark, & Gudmundsson, Joachim. Computing in Geometry and Topology. Computing in Geometry and Topology, 2 (). Retrieved from https://par.nsf.gov/biblio/10496292. https://doi.org/10.57717/cgt.v2i1.14
Aronov, Boris, Basit, Abdul, de Berg, Mark, and Gudmundsson, Joachim.
"Computing in Geometry and Topology". Computing in Geometry and Topology 2 (). Country unknown/Code not available: Computing in Geometry and Topology. https://doi.org/10.57717/cgt.v2i1.14.https://par.nsf.gov/biblio/10496292.
@article{osti_10496292,
place = {Country unknown/Code not available},
title = {Computing in Geometry and Topology},
url = {https://par.nsf.gov/biblio/10496292},
DOI = {10.57717/cgt.v2i1.14},
abstractNote = {Let L be a set of n axis-parallel lines in R3. We are are interested in partitions of R3 by a set H of three planes such that each open cell in the arrangement A(H) is intersected by as few lines from L as possible. We study such partitions in three settings, depending on the type of splitting planes that we allow. We obtain the following results. * There are sets L of n axis-parallel lines such that, for any set H of three splitting planes, there is an open cell in A(H) that intersects at least ⌊n/3⌋ - 1 ≈ n/3 lines. * If we require the splitting planes to be axis-parallel, then there are sets L of n axis-parallel lines such that, for any set H of three splitting planes, there is an open cell in A(H) that intersects at least (3/2) ⌊n/3⌋ - 1 ≈ (1/3 + 1/24) n lines. Furthermore, for any set L of n axis-parallel lines, there exists a set H of three axis-parallel splitting planes such that each open cell in A(H) intersects at most (7/18) n = (1/3 + 1/18) n lines. * For any set L of n axis-parallel lines, there exists a set H of three axis-parallel and mutually orthogonal splitting planes, such that each open cell in A(H) intersects at most ⌈5/12 n⌉ ≈ (1/3 + 1/12) n lines.},
journal = {Computing in Geometry and Topology},
volume = {2},
publisher = {Computing in Geometry and Topology},
author = {Aronov, Boris and Basit, Abdul and de Berg, Mark and Gudmundsson, Joachim},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
An official website of the United States government
