Search

We showthat the combinatorial complexity of the union of n "fat" tetrahedra in 3-space (i.e., tetrahedra all of whose solid angles are at least some fixed constant) of arbitrary sizes, is O(n2+ϵ), for any ϵ > 0; the bound is almost tight in the worst case, thus almost settling a conjecture of Pach et al. [2003]. Our result extends, in a significant way, the result of Pach et al. [2003] for the restricted case of nearly congruent cubes. The analysis uses cuttings, combined with the Dobkin-Kirkpatrick hierarchical decomposition of convex polytopes, in order to partition space into subcells, so that, on average, the overwhelming majority of the tetrahedra intersecting a subcell Δ behave as fat dihedral wedges in Δ. As an immediate corollary, we obtain that the combinatorial complexity of the union of n cubes in R³, having arbitrary side lengths, is O(n2+ϵ), for any ϵ > 0 (again, significantly extending the result of Pach et al. [2003]). Finally, our analysis can easily be extended to yield a nearly quadratic bound on the complexity of the union of arbitrarily oriented fat triangular prisms (whose cross-sections have arbitrary sizes) in R³. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the RMS distance (sum of squared distances between pairs of points) under translation between two point sets A and B, in the plane, with m=|B|≪n=|A|, in the partial-matching setup, in which each point in B is matched to a distinct point in A. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision DB,A of the plane and derive improved bounds on its complexity. Specifically, we show that this complexity is O(n2m3.5(elnm+e)m), so it is only quadratic in |A|. These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time. [ABSTRACT FROM AUTHOR]

Let p1, p2, p3 be three noncollinear points in the plane, and let P be a set of n other points in the plane. We show that the number of distinct distances between p1, p2, p3 and the points of P is Ω(n6/11), improving the lower bound Ω(n0.502) of Elekes and Szabó [4] (and considerably simplifying the analysis). [ABSTRACT FROM AUTHOR]

We show that, for any γ > 0, the combinatorial complexity of the union of n locally γ- fat objects of constant complexity in the plane is n/γ4 2O(log* n). For the special case of γ-fat triangles, the bound improves to O(n log* n + n/γ log² 1/γ). [ABSTRACT FROM AUTHOR]

Abstract: We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over any specific set of N points in the plane. More specifically, we bound the ratio between the number of spanning cycles (or perfect matchings) that can be embedded over a point set and the number of triangulations that can be embedded over it. The respective bounds are for cycles and for matchings. These imply a new upper bound of on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound ). Our analysis is based on a weighted variant of Kasteleynʼs linear algebra technique. [Copyright &y& Elsevier]

We show that the number of unit distances determined by n points in ℝ3 is O(n3/2), slightly improving the bound of Clarkson, Edelsbrunner, Guibas, Sharir and Welzl [5], established in 1990. The new proof uses the recently introduced polynomial partitioning technique of Guth and Katz [12]. While this paper was still in a draft stage, a similar proof of our main result was posted to the arXiv by Joshua Zahl [28]. [ABSTRACT FROM PUBLISHER]

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in ℝd, for d ≥ 3, is O(n2d-3 log n), improving Wenger's 20- year-old bound of O(n n2d-2). [ABSTRACT FROM AUTHOR]

Let P be a set of n points in ℝ3, and let k ≤ n be an integer. A sphere σ is k-rich with respect to P if |σ ∩ P| ≥ k, and is η-non-degenerate, for a fixed fraction 0 < η < 1, if no circle γ ⊂ σ contains more than η|σ ∩ P| points of P.We improve the previous bound given in [1] on the number of k-rich η-non-degenerate spheres in 3-space with respect to any set of n points in ℝ3, from O(n4/k5 + n3/k3), which holds for all 0 < η < 1/2, to O*(n4/k11/2 + n2/k2), which holds for all 0 < η < 1 (in both bounds, the constants of proportionality depend on η). The new bound implies the improved upper bound O*(n58/27) ≈ O(n2.1482) on the number of mutually similar triangles spanned by n points in ℝ3; the previous bound was O(n13/6) ≈ O(n2.1667) [1]. [ABSTRACT FROM AUTHOR]

In approximate halfspace range counting, one is given a set P of n points in ℝ, and an ε>0, and the goal is to preprocess P into a data structure which can answer efficiently queries of the form: Given a halfspace h, compute an estimate N such that (1− ε)| P∩ h|≤ N≤(1+ ε)| P∩ h|. Several recent papers have addressed this problem, including a study by Kaplan and Sharir (Proc. 17th Annu. ACM-SIAM Sympos. Discrete Algo., pp. 484-493, ), which is based, as is the present paper, on Cohen's technique for approximate range counting (Cohen in J. Comput. Syst. Sci. 55:441-453, ). In this approach, one chooses a small number of random permutations of P, and then constructs, for each permutation π, a data structure that answers efficiently minimum range queries: Given a query halfspace h, find the minimum-rank element (according to π) in P∩ h. By repeating this process for all chosen permutations, the approximate count can be obtained, with high probability, using a certain averaging process over the minimum-rank outputs. In the previous study, the authors have constructed such a data structure in ℝ, using a combinatorial result about the overlay of minimization diagrams in a randomized incremental construction of lower envelopes. In the present work, we propose an alternative approach to the range-minimum problem, based on cuttings, which achieves better performance. Specifically, it uses, for each permutation, O( n(log log n)/log n) expected storage and preprocessing time, for some constant c, and answers a range-minimum query in O(log n) expected time. We also present a different approach, based on 'antennas,' which is simple to implement, although the bounds on its expected storage, preprocessing, and query costs are worse by polylogarithmic factors. [ABSTRACT FROM AUTHOR]

We establish a bound of O(n2k1+ϵ), for any ϵ > 0, on the combinatorial complexity of the set T of line transversals of a collection P of k convex polyhedra in ℝ3 with a total of n facets, and we present a randomized algorithm which computes the boundary of T in comparable expected time. Thus, when k ⪡ n, the new bounds on the complexity (and construction cost) of T improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set Tℓ0 of line transversals which emanate from a fixed line ℓ0, establish an almost tight bound of O(nk1+ϵ) on the complexity of ℓ0 , and provide a randomized algorithm which computes ℓ0 in comparable expected time. Slightly improved combinatorial bounds for the complexity of ℓ0 and comparable improvements in the cost of constructing this set are established for two special cases, both assuming that the polyhedra of P are pairwise disjoint: the case where ℓ0 is disjoint from the polyhedra of P, and the case where the polyhedra of P are unbounded in a direction parallel to ℓ0. Our result is related to the problem of bounding the number of geometric permutations of a collection C of k pairwise-disjoint convex sets in ℝ3, namely, the number of distinct orders in which the line transversals of C visit its members. We obtain a new partial result on this problem. [ABSTRACT FROM AUTHOR]

Abstract: Let S be a set of n points in the plane, and let T be a set of m triangles with vertices in S. Then there exists a point in the plane contained in triangles of T. Eppstein [D. Eppstein, Improved bounds for intersecting triangles and halving planes, J. Combin. Theory Ser. A 62 (1993) 176–182] gave a proof of this claim, but there is a problem with his proof. Here we provide a correct proof by slightly modifying Eppstein''s argument. [Copyright &y& Elsevier]

Given a set S of n points in ℝ³, a point x in ℝ³ is called center point of S if every closed halfspace whose bounding hyperplane passes through x contains at least [n/4] points from S. We present a near-quadratic algorithm for computing the center region, that is, the set of all center points, of a set of n points in ℝ³. This is nearly tight in the worst case since the center region can have Ω(n²) complexity. We then consider sets S of 3n points in the plane which are the union of three disjoint sets consisting respectively of n red, n blue, and n green points. A point x in ℝ² is called a colored Tverberg point of S if there is a partition of S into n triples with one point of each color, so that x lies in all triangles spanned by these triples. We present a first polynomial-time algorithm for recognizing whether a given point is a colored Tverberg point of such a 3-colored set S. [ABSTRACT FROM AUTHOR]

We show that a set of n points in the plane has at most O(10.05n) perfect matchings with crossing-free straight-line embedding. The expected number of perfect crossing-free matchings of a set of n points drawn independently and identically distributed from an arbitrary distribution in the plane is at most O(9.24n). Several related bounds are derived: (a) The number of all (not necessarily perfect) crossing-free matchings is at most O(10.43n). (b) The number of red-blue perfect crossing-free matchings (where the points are colored red or blue and each edge of the matching must connect a red point with a blue point) is at most O(7.61n). (c) The number of left-right perfect crossing-free matchings (where the points are designated as left or right endpoints of the matching edges) is at most O(5.38n). (d) The number of perfect crossing-free matchings across a line (where all the matching edges must cross a fixed halving line of the set) is at most 4n. These bounds are employed to infer that a set of n points in the plane has at most O(86.81n) crossing-free spanning cycles (simple polygonizations) and at most O(12.24n) crossing-free partitions (these are partitions of the point set so that the convex hulls of the individual parts are pairwise disjoint). We also derive lower bounds for some of these quantities. [ABSTRACT FROM AUTHOR]

We show that the maximum number of occurrences of a given angle in a set of $n$ points in $\mathbb{R}^3$ is $O(n^{7/3})$ and that a right angle can actually occur $\Omega(n^{7/3})$ times. We then show that the maximum number of occurrences of any angle different from $\pi/2$ in a set of $n$ points in $\mathbb{R}^4$ is $O(n^{5/2}\beta(n))$, where $\beta(n) = 2^{O(\alpha(n)^2)}$ and $\alpha(n)$ is the inverse Ackermann function. [ABSTRACT FROM AUTHOR]

Let G be a topological graph with n vertices, i.e., a graph drawn in the plane with edges drawn as simple Jordan curves. It is shown that, for any constants k, l, there exists another constant C( k, l), such that if G has at least C( k, l) n edges, then it contains a k× l-gridlike configuration, that is, it contains k+ l edges such that each of the first k edges crosses each of the last l edges. Moreover, one can require the first k edges to be incident to the same vertex. [ABSTRACT FROM AUTHOR]

Abstract: We prove that, for every family of n semi-algebraic sets in of constant description complexity, there exist a positive constant that depends on the maximum complexity of the elements of , and two subfamilies with at least elements each, such that either every element of intersects all elements of or no element of intersects any element of . This implies the existence of another constant such that has a subset with elements, so that either every pair of elements of intersect each other or the elements of are pairwise disjoint. The same results hold when the intersection relation is replaced by any other semi-algebraic relation. We apply these results to settle several problems in discrete geometry and in Ramsey theory. [Copyright &y& Elsevier]