Personal tools
You are here: Home CG seminar 2018 On the Complexity of k-Level in Arrangements of Planes
« December 2018 »
December
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
Log in


Forgot your password?
 

On the Complexity of k-Level in Arrangements of Planes

Wednesday, May 30th, 2018, 16:10

Schreiber 309

underline

On the Complexity of k-Level in Arrangements of Planes

Chen Ziv, TAU

Abstract: 

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