K-set (geometry)

In discrete geometry, 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. More generally, in Euclidean space of higher dimensions, a "k"-set of a finite point set is a subset of "k" elements that can be separated from the remaining points by a hyperplane. In particular, when "k" = "n"/2 (where "n" is the size of "S"), the line or hyperplane that separates a "k"-set from the rest of "S" is a halving line or halving plane.

"K"-sets are related by projective duality to "k"-levels in line arrangements; the "k"-level in an arrangement of "n" lines in the plane is the curve consisting of the points that lie on one of the lines and have exactly "k" lines above them. Discrete and computational geometers have also studied levels in arrangements of more general kinds of curves and surfaces. [Agarwal et al. (1997); Chan (2003; 2005a,b).]

Combinatorial bounds

It is of importance in the analysis of geometric algorithms to bound the number of "k"-sets of a planar point set, [Chazelle and Preparata (1986); Cole et al. (1987); Edelsbrunner and Welzl (1986).] or equivalently the number of "k"-levels of a planar line arrangement, a problem first studied by Lovász (1971) and Erdős et al. (1973). The best known upper bound for this problem is "O"("nk"^1/3), as was shown by Tamal Dey (1998) using the crossing number inequality of Ajtai, Chvátal, Newborn, and Szemerédi. However, the best known lower bound is far from Dey's upper bound: it is Ω("n" exp("c" (log"k")^1/2)) for some constant "c", as shown by Toth (2001).

In three dimensions, the best upper bound known is "O"("nk"^3/2), and the best lower bound known is Ω("nk" exp("c" (log"k")^1/2)). [Sharir et al. (2001).]

For the case when "k" = "n"/2 (halving lines), the maximum number of combinatorially distinct lines through two points of "S" that bisect the remaining points when "k" = 1, 2, ... is:1,3,6,9,13,18,22... OEIS|id=A076523.

Bounds have also been proven on the number of ≤"k"-sets, where a ≤"k"-set is a "j"-set for some "j" ≤ "k". In two dimensions, the maximum number of ≤"k"-sets is exactly "nk", [Alon and Győri (1986).] while in "d" dimensions the bound is $O(n^\{lfloor\; d/2\; floor\}k^\{lceil\; d/2\; ceil\})$. [Clarkson and Shor (1989).]

Construction algorithms

Edelsbrunner and Welzl (1986) first studied the problem of constructing all "k"-sets of an input point set, or dually of constructing the "k"-level of an arrangement. The "k"-level version of their algorithm can be viewed as a plane sweep algorithm that constructs the level in left-to-right order. Viewed in terms of "k"-sets of point sets, their algorithm maintains a dynamic convex hull for the points on each side of a separating line, repeatedly finds a bitangent of these two hulls, and moves each of the two points of tangency to the opposite hull. Chan (1999) surveys subsequent results on this problem, and shows that it can be solved in time proportional to Dey's "O"("nk"^1/3) bound on the complexity of the "k"-level.

Agarwal and Matoušek describe algorithms for efficiently constructing an approximate level; that is, a curve that passes between the ("k" - "d")-level and the ("k" + "d")-level for some small approximation parameter "d". They show that such an approximation can be found, consisting of a number of line segments that depends only on "n"/"d" and not on "n" or "k". [Agarwal (1990); Matoušek (1990,1991).]

Matroid generalizations

The planar "k"-level problem can be generalized to one of parametric optimization in a matroid: one is given a matroid in which each element is weighted by a linear function of a parameter λ, and must find the minimum weight basis of the matroid for each possible value of λ. If one graphs the weight functions as lines in a plane, the "k"-level of the arrangement of these lines graphs as a function of λ the weight of the largest element in an optimal basis in a uniform matroid, and Dey showed that his "O"("nk"^1/3) bound on the complexity of the "k"-level could be generalized to count the number of distinct optimal bases of any matroid with "n" elements and rank "k".

For instance, the same "O"("nk"^1/3) upper bound holds for counting the number of different minimum spanning trees formed in a graph with "n" edges and "k" vertices, when the edges have weights that vary linearly with a parameter λ. This parametric minimum spanning tree problem has been studied by various authors and can be used to solve other bicriterion spanning tree optimization problems. [Gusfield (1980); Ishii et al. (1981); Katoh and Ibaraki (1983); Hassin and Tamir (1989); Fernández-Baca et al. (1996); Chan (2005c).]

However, the best known lower bound for the parametric minimum spanning tree problem is Ω("n" α("k")), where α is the inverse Ackermann function, an even weaker bound than that for the "k"-set problem. For more general matroids, Dey's "O"("nk"^1/3) upper bound has a matching lower bound. [Eppstein (1998).]

Notes

References

*cite journal
author = Agarwal, P. K.
title = Partitioning arrangements of lines I: An efficient deterministic algorithm
journal = Discrete and Computational Geometry
volume = 5
issue = 1
year = 1990
pages = 449–483
doi = 10.1007/BF02187805

*cite conference
author = Agarwal, P. K.; Aronov, B.; Sharir, M.
title = On levels in arrangements of lines, segments, planes, and triangles
booktitle = Proc. 13th Annual Symposium on Computational Geometry
year = 1997
pages = 30–38

*cite journal
author = Alon, N.; Győri,E.
title = The number of small semi-spaces of a finite set of points in the plane
journal = Journal of Combinatorial Theory, Series A
volume = 41
pages = 154–157
year = 1986
doi = 10.1016/0097-3165(86)90122-6

*cite journal
author = Chan, T. M.
title = Remarks on k-level algorithms in the plane
year = 1999
url = http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz

*cite journal
author = Chan, T. M.
title = On levels in arrangements of curves
journal = Discrete and Computational Geometry
volume = 29
pages = 375–393
year = 2003
doi = 10.1007/s00454-002-2840-2

*cite journal
author = Chan, T. M.
title = On levels in arrangements of curves, II: a simple inequality and its consequence
journal = Discrete and Computational Geometry
volume = 34
pages = 11–24
year = 2005a
*cite conference
author = Chan, T. M.
title = On levels in arrangements of surfaces in three dimensions
booktitle = Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms
pages = 232–240
year = 2005b
url = http://www.cs.uwaterloo.ca/~tmchan/surf_soda.ps
*cite conference
author = Chan, T. M.
title = Finding the shortest bottleneck edge in a parametric minimum spanning tree
booktitle = Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms
pages = 232–240
year = 2005c
url = http://www.cs.uwaterloo.ca/~tmchan/bottle_soda.ps

*cite journal
author = Chazelle, B.; Preparata, F. P.
title = Halfspace range search: an algorithmic application of "k"-sets
journal = Discrete and Computational Geometry
volume = 1
issue = 1
year = 1986
pages = 83–93
id = MathSciNet | id = 0824110
doi = 10.1007/BF02187685

*cite journal
author = Clarkson, K. L.; Shor, P.
title = Applications of random sampling, II
journal = Discrete and Computational Geometry
volume = 4
pages = 387–421
year = 1989
doi = 10.1007/BF02187740

*cite journal
author = Cole, R.; Sharir, M.; Yap, C. K.
title = On "k"-hulls and related problems
journal = SIAM Journal on Computing
volume = 16
issue = 1
year = 1987
pages = 61–77
id = MathSciNet | id = 0873250
doi = 10.1137/0216005

*cite journal
author = Dey, T. L.
title = Improved bounds for planar "k"-sets and related problems
journal = Discrete and Computational Geometry
volume = 19
issue = 3
year = 1998
pages = 373–382
doi = 10.1007/PL00009354
id = MathSciNet | id = 1608878

*cite journal
author = Edelsbrunner, H.; Welzl, E.
title = Constructing belts in two-dimensional arrangements with applications
journal = SIAM Journal on Computing
volume = 15
issue = 1
year = 1986
pages = 271–284
doi = 10.1137/0215019

*cite journal
title = Geometric lower bounds for parametric matroid optimization.
author = Eppstein, D.
authorlink = David Eppstein
journal = Discrete and Computational Geometry
volume = 20
pages = 463–476
year = 1998
url = http://www.ics.uci.edu/~eppstein/pubs/Epp-DCG-98.pdf
doi = 10.1007/PL00009396

*cite conference
author = Erdős, P.; Lovász, L.; Simmons, A.; Straus, E. G.
title = Dissection graphs of planar point sets
booktitle = A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971)
publisher = North-Holland
location = Amsterdam
date = 1973
pages = 139–149
id = MathSciNet | id = 0363986

*cite journal
title = Using sparsification for parametric minimum spanning tree problems
author = Fernández-Baca, D.; Slutzki, G.; Eppstein, D.
journal = Nordic Journal of Computing
volume = 3
issue = 4
pages = 352–366
year = 1996

*cite paper
author = Gusfield, D.
title = Sensitivity analysis for combinatorial optimization
version = Tech. Rep. UCB/ERL M80/22
publisher = University of California, Berkeley
date = 1980

*cite journal
author = Hassin, R.; Tamir, A.
title = Maximizing classes of two-parametric objectives over matroids
journal = Math. Oper. Res.
volume = 14
pages = 362–375
year = 1989

*cite journal
author = Ishii, H.; Shiode, S.; Nishida, T.
title = Stochastic spanning tree problem
journal = Discrete Applied Mathematics
volume = 3
pages = 263–273
year = 1981
doi = 10.1016/0166-218X(81)90004-4

*cite paper
author = Katoh, N.; Ibaraki, T.
title = On the total number of pivots required for certain parametric combinatorial optimization problems
version = Working Paper 71
publisher = Inst. Econ. Res., Kobe Univ. of Commerce
date = 1983

*cite journal
author = Lovász, L.
title = On the number of halving lines
journal = Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica
volume = 14
year = 1971
pages = 107–108

*cite journal
author = Matoušek, J.
title = Construction of ε-nets
journal = Discrete and Computational Geometry
volume = 5
issue = 5
year = 1990
pages = 427–448
id = MathSciNet | id = 1064574
doi = 10.1007/BF02187804

*cite journal
author = Matoušek, J.
title = Approximate levels in line arrangements
journal = SIAM Journal on Computing
volume = 20
issue = 2
pages = 222–227
year = 1991
doi = 10.1137/0220013

*cite journal
author = Sharir, M.; Smorodinsky, S.; Tardos, G.
title = An improved bound for "k"-sets in three dimensions
journal = Discrete and Computational Geometry
volume = 26
year = 2001
pages = 195–204
doi = 10.1007/s00454-001-0005-3

*cite journal
author = Tóth, G.
title = Point sets with many "k"-sets
journal = Discrete and Computational Geometry
volume = 26
issue = 2
pages = 187–194
year = 2001
doi = 10.1007/s004540010022

External links

* [http://compgeom.cs.uiuc.edu/~jeffe/open/ksets.html Halving lines and k-sets] , Jeff Erickson
* [http://maven.smith.edu/~orourke/TOPP/P7.html The Open Problems Project, Problem 7: "k"-sets]