K-set (geometry)

From HandWiki
Short description: Points separated from others by a line
A set of six points (red), its six 2-sets (the sets of points contained in the blue ovals), and lines separating each [math]\displaystyle{ k }[/math]-set from the remaining points (dashed black).

In discrete geometry, a [math]\displaystyle{ k }[/math]-set of a finite point set [math]\displaystyle{ S }[/math] in the Euclidean plane is a subset of [math]\displaystyle{ k }[/math] elements of [math]\displaystyle{ S }[/math] that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a [math]\displaystyle{ k }[/math]-set of a finite point set is a subset of [math]\displaystyle{ k }[/math] elements that can be separated from the remaining points by a hyperplane. In particular, when [math]\displaystyle{ k=n/2 }[/math] (where [math]\displaystyle{ n }[/math] is the size of [math]\displaystyle{ S }[/math]), the line or hyperplane that separates a [math]\displaystyle{ k }[/math]-set from the rest of [math]\displaystyle{ S }[/math] is a halving line or halving plane.

The [math]\displaystyle{ k }[/math]-sets of a set of points in the plane are related by projective duality to the [math]\displaystyle{ k }[/math]-levels in an arrangement of lines. The [math]\displaystyle{ k }[/math]-level in an arrangement of [math]\displaystyle{ n }[/math] lines in the plane is the curve consisting of the points that lie on one of the lines and have exactly [math]\displaystyle{ k }[/math] lines below them. Discrete and computational geometers have also studied levels in arrangements of more general kinds of curves and surfaces.[1]

Combinatorial bounds

Question, Web Fundamentals.svg Unsolved problem in mathematics:
What is the largest possible number of halving lines for a set of [math]\displaystyle{ n }[/math] points in the plane?
(more unsolved problems in mathematics)

It is of importance in the analysis of geometric algorithms to bound the number of [math]\displaystyle{ k }[/math]-sets of a planar point set,[2] or equivalently the number of [math]\displaystyle{ k }[/math]-levels of a planar line arrangement, a problem first studied by Lovász[3] and Erdős et al.[4] The best known upper bound for this problem is [math]\displaystyle{ O(nk^{1/3}) }[/math], as was shown by Tamal Dey[5] 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 [math]\displaystyle{ \Omega(nc^{\sqrt{\log k}}) }[/math] for some constant [math]\displaystyle{ c }[/math], as shown by Tóth.[6]

In three dimensions, the best upper bound known is [math]\displaystyle{ O(nk^{3/2}) }[/math], and the best lower bound known is [math]\displaystyle{ \Omega(nkc^{\sqrt{\log k}}) }[/math].[7] For points in three dimensions that are in convex position, that is, are the vertices of some convex polytope, the number of [math]\displaystyle{ k }[/math]-sets is [math]\displaystyle{ \Theta\bigl((n-k)k\bigr) }[/math], which follows from arguments used for bounding the complexity of [math]\displaystyle{ k }[/math]th order Voronoi diagrams.[8]

For the case when [math]\displaystyle{ k=n/2 }[/math] (halving lines), the maximum number of combinatorially distinct lines through two points of [math]\displaystyle{ S }[/math] that bisect the remaining points when [math]\displaystyle{ k=1,2,\dots }[/math] is

1,3,6,9,13,18,22... (sequence A076523 in the OEIS).

Bounds have also been proven on the number of [math]\displaystyle{ \le k }[/math]-sets, where a [math]\displaystyle{ \le k }[/math]-set is a [math]\displaystyle{ j }[/math]-set for some [math]\displaystyle{ j\le k }[/math]. In two dimensions, the maximum number of [math]\displaystyle{ \le k }[/math]-sets is exactly [math]\displaystyle{ nk }[/math],[9] while in [math]\displaystyle{ d }[/math] dimensions the bound is [math]\displaystyle{ O(n^{\lfloor d/2\rfloor}k^{\lceil d/2\rceil}) }[/math].[10]

Construction algorithms

Edelsbrunner and Welzl[11] first studied the problem of constructing all [math]\displaystyle{ k }[/math]-sets of an input point set, or dually of constructing the [math]\displaystyle{ k }[/math]-level of an arrangement. The [math]\displaystyle{ k }[/math]-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 [math]\displaystyle{ k }[/math]-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[12] surveys subsequent results on this problem, and shows that it can be solved in time proportional to Dey's [math]\displaystyle{ O(nk^{1/3}) }[/math] bound on the complexity of the [math]\displaystyle{ k }[/math]-level.

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

Matroid generalizations

The planar [math]\displaystyle{ k }[/math]-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 [math]\displaystyle{ \lambda }[/math], and must find the minimum weight basis of the matroid for each possible value of [math]\displaystyle{ \lambda }[/math]. If one graphs the weight functions as lines in a plane, the [math]\displaystyle{ k }[/math]-level of the arrangement of these lines graphs as a function of [math]\displaystyle{ \lambda }[/math] the weight of the largest element in an optimal basis in a uniform matroid, and Dey showed that his [math]\displaystyle{ O(nk^{1/3}) }[/math] bound on the complexity of the [math]\displaystyle{ k }[/math]-level could be generalized to count the number of distinct optimal bases of any matroid with [math]\displaystyle{ n }[/math] elements and rank [math]\displaystyle{ k }[/math].

For instance, the same [math]\displaystyle{ O(nk^{1/3}) }[/math] upper bound holds for counting the number of different minimum spanning trees formed in a graph with [math]\displaystyle{ n }[/math] edges and [math]\displaystyle{ k }[/math] vertices, when the edges have weights that vary linearly with a parameter [math]\displaystyle{ \lambda }[/math]. This parametric minimum spanning tree problem has been studied by various authors and can be used to solve other bicriterion spanning tree optimization problems.[14]

However, the best known lower bound for the parametric minimum spanning tree problem is [math]\displaystyle{ \Omega(n\log k) }[/math], a weaker bound than that for the [math]\displaystyle{ k }[/math]-set problem.[15] For more general matroids, Dey's [math]\displaystyle{ O(nk^{1/3}) }[/math] upper bound has a matching lower bound.[16]

Notes

  1. ↑ (Agarwal Aronov); (Chan 2003); (Chan 2005a); (Chan 2005b).
  2. ↑ (Chazelle Preparata); (Cole Sharir); (Edelsbrunner Welzl).
  3. ↑ Lovász 1971.
  4. ↑ Erdős et al. 1973.
  5. ↑ Dey 1998.
  6. ↑ Tóth 2001.
  7. ↑ Sharir, Smorodinsky & Tardos 2001.
  8. ↑ (Lee 1982); (Clarkson Shor).
  9. ↑ Alon & Győri 1986.
  10. ↑ Clarkson & Shor 1989.
  11. ↑ Edelsbrunner & Welzl 1986.
  12. ↑ Chan 1999.
  13. ↑ (Agarwal 1990); (Matoušek 1990); (Matoušek 1991).
  14. ↑ (Gusfield 1980); (Ishii Shiode); (Katoh Ibaraki); (Hassin Tamir); (Fernández-Baca Slutzki); (Chan 2005c).
  15. ↑ Eppstein 2022.
  16. ↑ Eppstein 1998.

References

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=K-set_(geometry)&oldid=3378011"