Personal tools
You are here: Home CG seminar 2018 On the Complexity of k-Level in Arrangements of Planes
« June 2018 »
Log in

Forgot your password?

On the Complexity of k-Level in Arrangements of Planes

Wednesday, May 30th, 2018, 16:10

Schreiber 309


On the Complexity of k-Level in Arrangements of Planes

Chen Ziv, TAU


A k-set of a finite point set S in the Euclidean plane is a subset of k elements of S that can be strictly separated from the remaining points by a line. We discuss the problem of bounding the complexity of the number of k-sets in a set of n points. This problem was first studied by Lovász in 1971 and by Erdős et al. in 1973. It is an open problem to bound the complexity of the number of k-sets, and there is a big gap between the lower bound and the upper bound known today. This problem has many versions and generalizations, which some of them we introduce.


We discuss a dual version of the problem in R^3: let A be a set of n non-vertical planes in R^3, in general position. We say that a point p lies at level k of the arrangement of A, if exactly k planes of A pass below p. Our goal is to obtain an upper bound on the complexity of the k-level of the arrangement of A. We introduce a dual version of a technique, setting and bounds that are based on a simple version of a result presented in “An improved bound for k-sets in three dimensions” by Sharir, Smorodinsky and Tardos (1999), and show a known upper bound of O(nk^(5/3)).


Our work is in progress, and the goal is to generalize the result we show here for more complicated collection of objects.

Document Actions