- K-set (geometry)
In

discrete geometry , a "k"-set of a finite point set "S" in theEuclidean plane is asubset of "k" elements of "S" that can be strictly separated from the remaining points by aline . More generally, inEuclidean 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 ahyperplane . 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 thecrossing 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 adynamic convex hull for the points on each side of a separating line, repeatedly finds abitangent 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 differentminimum spanning tree s 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*]

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Geometry**— (Greek γεωμετρία ; geo = earth, metria = measure) is a part of mathematics concerned with questions of size, shape, and relative position of figures and with properties of space. Geometry is one of the oldest sciences. Initially a body of… … Wikipedia**Geometry & Topology**— (ISSN 1364 0380 online, 1465 3060 printed) is a peer refereed, international mathematics research journal devoted to geometry and topology, and their applications. It is currently based at the University of Warwick, United Kingdom, and published… … Wikipedia**geometry**— /jee om i tree/, n. 1. the branch of mathematics that deals with the deduction of the properties, measurement, and relationships of points, lines, angles, and figures in space from their defining conditions by means of certain assumed properties… … Universalium**Set theory**— This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects … Wikipedia**set theory**— the branch of mathematics that deals with relations between sets. [1940 45] * * * Branch of mathematics that deals with the properties of sets. It is most valuable as applied to other areas of mathematics, which borrow from and adapt its… … Universalium**Geometry Wars**— Infobox VG title=Geometry Wars developer=Bizarre Creations publisher=Microsoft Game Studios distributor=Microsoft Game Studios (retail) Microsoft Game Studios/Valve Corporation (Steam) designer=Stephen Cakey Cakebread engine= released=Xbox… … Wikipedia**Geometry and topology**— In mathematics, geometry and topology is an umbrella term for geometry and topology, as the line between these two is often blurred, most visibly in local to global theorems in Riemannian geometry, and results like the Gauss–Bonnet theorem and… … Wikipedia**geometry**— Although various laws concerning lines and angles were known to the Egyptians and the Pythagoreans, the systematic treatment of geometry by the axiomatic method began with the Elements of Euclid . From a small number of explicit axioms,… … Philosophy dictionary**Geometry of numbers**— In number theory, the geometry of numbers is a topic and method arising from the work of Hermann Minkowski, on the relationship between convex sets and lattices in n dimensional space. It has frequently been used in an auxiliary role in proofs,… … Wikipedia**Geometry (album)**— Infobox Album Name = Geometry Type = studio Longtype = Artist = Robert Rich Released = 1991 Recorded = 1986 1987 in Menlo Park, California Genre = Ambient Length = 68:00 Label = Spalax Producer = Robert Rich Reviews = *Allmusic Rating|4|5… … Wikipedia