K-set (geometry)

Image:k-sets.svg

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.

The $k$ -sets of a set of points in the plane are related by projective duality to the $k$ -levels in an arrangement of lines. 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 below them. Discrete and computational geometers have also studied levels in arrangements of more general kinds of curves and surfaces.{{harvtxt|Agarwal|Aronov|Sharir|1997}}; {{harvtxt|Chan|2003}}; {{harvtxt|Chan|2005a}}; {{harvtxt|Chan|2005b}}.

Combinatorial bounds

{{unsolved|mathematics|What is the largest possible number of halving lines for a set of $n$ points in the plane?}}

It is of importance in the analysis of geometric algorithms to bound the number of $k$ -sets of a planar point set,{{harvtxt|Chazelle|Preparata|1986}}; {{harvtxt|Cole|Sharir|Yap|1987}}; {{harvtxt|Edelsbrunner|Welzl|1986}}. or equivalently the number of $k$ -levels of a planar line arrangement, a problem first studied by Lovász{{sfn|Lovász|1971}} and Erdős et al.{{sfn|Erdős|Lovász|Simmons|Straus|1973}} The best known upper bound for this problem is $O(nk^{1/3})$ , as was shown by Tamal Dey{{sfn|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 $\Omega(nc^{\sqrt{\log k}})$ for some constant $c$ , as shown by Tóth.{{sfn|Tóth|2001}}

In three dimensions, the best upper bound known is $O(nk^{3/2})$ , and the best lower bound known is $\Omega(nkc^{\sqrt{\log k}})$ .{{sfn|Sharir|Smorodinsky|Tardos|2001}}

For points in three dimensions that are in convex position, that is, are the vertices of some convex polytope, the number of $k$ -sets is

$\Theta\bigl((n-k)k\bigr)$ , which follows from arguments used for bounding the complexity of $k$ th order Voronoi diagrams.{{harvtxt|Lee|1982}}; {{harvtxt|Clarkson|Shor|1989}}.

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,\dots$ is

{{bi|left=1.6|1,3,6,9,13,18,22... {{OEIS|id=A076523}}.}}

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

Construction algorithms

Edelsbrunner and Welzl{{sfn|Edelsbrunner|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{{sfn|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-\delta)$ -level and the $(k+\delta)$ -level for some small approximation parameter $\delta$ . They show that such an approximation can be found, consisting of a number of line segments that depends only on $n/\delta$ and not on $n$ or $k$ .{{harvtxt|Agarwal|1990}}; {{harvtxt|Matoušek|1990}}; {{harvtxt|Matoušek|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 $\lambda$ , and must find the minimum weight basis of the matroid for each possible value of $\lambda$ . 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 $\lambda$ 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 $\lambda$ . This parametric minimum spanning tree problem has been studied by various authors and can be used to solve other bicriterion spanning tree optimization problems.{{harvtxt|Gusfield|1980}}; {{harvtxt|Ishii|Shiode|Nishida|1981}}; {{harvtxt|Katoh|Ibaraki|1983}}; {{harvtxt|Hassin|Tamir|1989}}; {{harvtxt|Fernández-Baca|Slutzki|Eppstein|1996}}; {{harvtxt|Chan|2005c}}.

However, the best known lower bound for the parametric minimum spanning tree problem is $\Omega(n\log k)$ , a weaker bound than that for the $k$ -set problem.{{sfn|Eppstein|2022}} For more general matroids, Dey's $O(nk^{1/3})$ upper bound has a matching lower bound.{{sfn|Eppstein|1998}}

Notes

References

{{cite journal

| last = Agarwal | first = P. K. | author-link = Pankaj K. Agarwal

| title = Partitioning arrangements of lines I: An efficient deterministic algorithm

| journal = Discrete & Computational Geometry

| volume = 5

| issue = 1

| year = 1990

| pages = 449–483

| doi = 10.1007/BF02187805 | doi-access = free

}}

{{cite conference

| last1 = Agarwal | first1 = P. K. | author1-link = Pankaj K. Agarwal

| last2 = Aronov | first2 = B. | author2-link = Boris Aronov

| last3 = Sharir | first3 = M. | author3-link = Micha Sharir

| title = On levels in arrangements of lines, segments, planes, and triangles

| book-title = Proc. 13th Annual Symposium on Computational Geometry

| year = 1997

| pages = 30–38}}

{{cite journal

| last1 = Alon | first1 = N. | author1-link = Noga Alon

| last2 = Győri | first2 = E.

| title = The number of small semi-spaces of a finite set of points in the plane

| journal = Journal of Combinatorial Theory | series=Series A

| volume = 41

| pages = 154–157

| year = 1986

| doi = 10.1016/0097-3165(86)90122-6| doi-access = free}}

{{cite web

|last = Chan

|first = T. M.

|author-link = Timothy M. Chan

|title = Remarks on {{mvar|k}}-level algorithms in the plane

|year = 1999

|url = http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz

|url-status = dead

|archive-url = https://web.archive.org/web/20101104182509/http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz

|archive-date = 2010-11-04

}}

{{cite journal

| last = Chan | first = T. M. | author-link = Timothy M. Chan

| title = On levels in arrangements of curves

| journal = Discrete & Computational Geometry

| volume = 29

| pages = 375–393

| year = 2003

| doi = 10.1007/s00454-002-2840-2

| issue = 3 | doi-access = free

}}

{{cite journal

| last = Chan | first = T. M. | author-link = Timothy M. Chan

| title = On levels in arrangements of curves, II: a simple inequality and its consequence

| journal = Discrete & Computational Geometry

| volume = 34

| pages = 11–24

| year = 2005a

| doi = 10.1007/s00454-005-1165-3 | doi-access = free

}}

{{cite conference

| last = Chan | first = T. M. | author-link = Timothy M. Chan

| title = On levels in arrangements of surfaces in three dimensions

| book-title = 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

| last = Chan | first = T. M. | author-link = Timothy M. Chan

| title = Finding the shortest bottleneck edge in a parametric minimum spanning tree

| book-title = 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

| last1 = Chazelle | first1 = B. | author1-link = Bernard Chazelle

| last2 = Preparata | first2 = F. P. | author2-link = Franco Preparata

| title = Halfspace range search: an algorithmic application of {{mvar|k}}-sets

| journal = Discrete & Computational Geometry

| volume = 1

| issue = 1

| year = 1986

| pages = 83–93

|mr=0824110

| doi = 10.1007/BF02187685 | doi-access = free

}}

{{cite journal

| last1 = Clarkson | first1 = K. L. | author1-link = Kenneth L. Clarkson

| last2 = Shor | first2 = P. | author2-link = Peter Shor

| title = Applications of random sampling, II

| journal = Discrete & Computational Geometry

| volume = 4

| pages = 387–421

| year = 1989

| doi = 10.1007/BF02187740 | doi-access = free

}}

{{cite journal

| last1 = Cole | first1 = R.

| last2 = Sharir | first2 = M. | author2-link = Micha Sharir

| last3 = Yap | first3 = C. K.

| title = On {{mvar|k}}-hulls and related problems

| journal = SIAM Journal on Computing

| volume = 16

| issue = 1

| year = 1987

| pages = 61–77

|mr=0873250

| doi = 10.1137/0216005}}

{{cite journal

| last = Dey | first = T. K. | author-link = Tamal Dey

| title = Improved bounds for planar {{mvar|k}}-sets and related problems

| journal = Discrete & Computational Geometry

| volume = 19

| issue = 3

| year = 1998

| pages = 373–382

| doi = 10.1007/PL00009354

| mr=1608878 | doi-access = free

}}

{{cite journal

| last1 = Edelsbrunner | first1 = H. | author1-link = Herbert Edelsbrunner

| last2 = Welzl | first2 = E. | author2-link = Emo Welzl

| 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

| last = Eppstein | first = D. | author-link = David Eppstein

| journal = Discrete & 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 | doi-access = free

| issue = 4}}

{{cite journal

| last = Eppstein | first = David

| date = August 2022

| doi = 10.1007/s00453-022-01024-9

| journal = Algorithmica

| title = A stronger lower bound on parametric minimum spanning trees| volume = 85

| issue = 6

| pages = 1738–1753

| doi-access = free

| arxiv = 2105.05371

}}

{{cite conference

| title = Dissection graphs of planar point sets

| book-title = 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

|mr=0363986}}

{{cite journal

| title = Using sparsification for parametric minimum spanning tree problems

| journal = Nordic Journal of Computing

| volume = 3

| issue = 4

| pages = 352–366

| year = 1996}}

{{cite book

| last1 = Gusfield | first1 = D.

| title = Sensitivity analysis for combinatorial optimization

| series = Tech. Rep. UCB/ERL M80/22

| publisher = University of California, Berkeley

| date = 1980}}

{{cite journal

| last1=Hassin | first1=R.

| last2=Tamir | first2=A.

| title=Maximizing classes of two-parametric objectives over matroids

| journal=Mathematics of Operations Research

| volume=14

| pages=362–375

| year=1989

| doi=10.1287/moor.14.2.362

| issue=2}}

{{cite journal

| title = Stochastic spanning tree problem

| journal = Discrete Applied Mathematics

| volume = 3

| pages = 263–273

| year = 1981

| doi = 10.1016/0166-218X(81)90004-4

| issue = 4| doi-access = free

}}

{{cite book

| series = Working Paper 71

| publisher = Inst. Econ. Res., Kobe Univ. of Commerce

| date = 1983}}

{{cite journal

| last = Lee | first = Der-Tsai | author-link = Der-Tsai Lee

| title = On {{mvar|k}}-nearest neighbor Voronoi diagrams in the plane

| journal = IEEE Transactions on Computers

| volume = 31

| year = 1982

| pages = 478–487

| doi = 10.1109/TC.1982.1676031

| issue = 6}}

{{cite journal

| last1=Lovász | first1 =L. | authorlink1=László Lovász

| 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

| last = Matoušek | first = J. | author-link = Jiří Matoušek (mathematician)

| title = Construction of {{mvar|ε}}-nets

| journal = Discrete & Computational Geometry

| volume = 5

| issue = 5

| year = 1990

| pages = 427–448

|mr=1064574

| doi = 10.1007/BF02187804| doi-access = free

}}

{{cite journal

| last = Matoušek | first = J. | author-link = Jiří Matoušek (mathematician)

| 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

| title = An improved bound for {{mvar|k}}-sets in three dimensions

| journal = Discrete & Computational Geometry

| volume = 26

| year = 2001

| issue=2 | pages = 195–204

| doi = 10.1007/s00454-001-0005-3| doi-access = free

}}

{{cite journal

| last1 = Tóth | first1 = G.

| title = Point sets with many {{mvar|k}}-sets

| journal = Discrete & Computational Geometry

| volume = 26

| issue = 2

| pages = 187–194

| year = 2001

| doi = 10.1007/s004540010022| doi-access = free

}}

External links

[http://compgeom.cs.uiuc.edu/~jeffe/open/ksets.html Halving lines and {{mvar|k}}-sets], Jeff Erickson
[https://web.archive.org/web/20070703103435/http://maven.smith.edu/~orourke/TOPP/P7.html The Open Problems Project, Problem 7: {{mvar|k}}-sets]

Category:Discrete geometry

Category:Matroid theory