K-set (geometry)

Last updated January 03, 2024

A set of six points (red), its six 2-sets (the sets of points contained in the blue ovals), and lines separating each
k
{\displaystyle k}
-set from the remaining points (dashed black). K-sets.svg — A set of six points (red), its six 2-sets (the sets of points contained in the blue ovals), and lines separating each $k$ -set from the remaining points (dashed black).

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.^[1]

Combinatorial bounds

Unsolved problem in mathematics:

What is the largest possible number of halving lines for a set of $n$ points in the plane?

(more unsolved problems in mathematics)

It is of importance in the analysis of geometric algorithms to bound the number of $k$ -sets of a planar point set,^[2] or equivalently the number of $k$ -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 $O(nk^{1/3})$ , 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 ${\textstyle \Omega (nc^{\sqrt {\log k}})}$ for some constant $c$ , as shown by Tóth.^[6]

In three dimensions, the best upper bound known is $O(nk^{3/2})$ , and the best lower bound known is ${\textstyle \Omega (nkc^{\sqrt {\log k}})}$ .^[7] 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.^[8]

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

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

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

Construction algorithms

Edelsbrunner and Welzl^[11] 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^[12] 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$ .^[13]

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.^[14]

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.^[15] For more general matroids, Dey's $O(nk^{1/3})$ upper bound has a matching lower bound.^[16]

Related Research Articles

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Arrangement of lines</span> Subdivision of the plane by lines

In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.

The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. It is named after James Joseph Sylvester, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944.

<span class="mw-page-title-main">No-three-in-line problem</span> Geometry problem on grid points

The no-three-in-line problem in discrete geometry asks how many points can be placed in the $grid so that no three points lie on the same line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".$

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input data elements may be inserted, deleted, or modified. It should be distinguished from the kinetic convex hull, which studies similar problems for continuously moving points. Dynamic convex hull problems may be distinguished by the types of the input data and the allowed types of modification of the input data.

Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.

In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of $line segments with crossings, the Bentley-Ottmann algorithm takes time . In cases where, this is an improvement on a naïve algorithm that tests every pair of segments, which takes .$

In mathematics, the vertex enumeration problem for a polytope, a polyhedral cell complex, a hyperplane arrangement, or some other object of discrete geometry, is the problem of determination of the object's vertices given some formal representation of the object. A classical example is the problem of enumeration of the vertices of a convex polytope specified by a set of linear inequalities:

Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the Journal of Computational Geometry.

In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection problem is to find a common independent set with the maximum possible weight. These problems generalize many problems in combinatorial optimization including finding maximum matchings and maximum weight matchings in bipartite graphs and finding arborescences in directed graphs.

In non-parametric statistics, the Theil–Sen estimator is a method for robustly fitting a line to sample points in the plane by choosing the median of the slopes of all lines through pairs of points. It has also been called Sen's slope estimator, slope selection, the single median method, the Kendall robust line-fit method, and the Kendall–Theil robust line. It is named after Henri Theil and Pranab K. Sen, who published papers on this method in 1950 and 1968 respectively, and after Maurice Kendall because of its relation to the Kendall tau rank correlation coefficient.

In the study of algorithms, an LP-type problem is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.

In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as points in the Euclidean plane and edges are represented as line segments that do not pass through any non-incident vertex.

<span class="mw-page-title-main">Topological graph</span>

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

In graph theory, a branch of mathematics, a $t$ -biclique-free graph is a graph that has no $2t$ -vertex complete bipartite graph $K t, t$ as a subgraph. A family of graphs is biclique-free if there exists a number $t$ such that the graphs in the family are all $t$ -biclique-free. The biclique-free graph families form one of the most general types of sparse graph family. They arise in incidence problems in discrete geometry, and have also been used in parameterized complexity.

In the design and analysis of algorithms for combinatorial optimization, parametric search is a technique invented by Nimrod Megiddo (1983) for transforming a decision algorithm into an optimization algorithm. It is frequently used for solving optimization problems in computational geometry.

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

In geometry, the zone theorem is a result that establishes the complexity of the zone of a line in an arrangement of lines.

References

Agarwal, P. K. (1990). "Partitioning arrangements of lines I: An efficient deterministic algorithm". Discrete & Computational Geometry . 5 (1): 449–483. doi: 10.1007/BF02187805 .
Agarwal, P. K.; Aronov, B.; Sharir, M. (1997). "On levels in arrangements of lines, segments, planes, and triangles". Proc. 13th Annual Symposium on Computational Geometry. pp. 30–38.
Alon, N.; Győri, E. (1986). "The number of small semi-spaces of a finite set of points in the plane". Journal of Combinatorial Theory . Series A. 41: 154–157. doi: 10.1016/0097-3165(86)90122-6 .
Chan, T. M. (1999). "Remarks on $k$ -level algorithms in the plane". Archived from the original on 2010-11-04.
Chan, T. M. (2003). "On levels in arrangements of curves". Discrete & Computational Geometry . 29 (3): 375–393. doi: 10.1007/s00454-002-2840-2 .
Chan, T. M. (2005a). "On levels in arrangements of curves, II: a simple inequality and its consequence". Discrete & Computational Geometry . 34: 11–24. doi: 10.1007/s00454-005-1165-3 .
Chan, T. M. (2005b). "On levels in arrangements of surfaces in three dimensions". Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 232–240.
Chan, T. M. (2005c). "Finding the shortest bottleneck edge in a parametric minimum spanning tree". Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 232–240.
Chazelle, B.; Preparata, F. P. (1986). "Halfspace range search: an algorithmic application of $k$ -sets". Discrete & Computational Geometry . 1 (1): 83–93. doi: 10.1007/BF02187685 . MR 0824110.
Clarkson, K. L.; Shor, P. (1989). "Applications of random sampling, II". Discrete & Computational Geometry . 4: 387–421. doi: 10.1007/BF02187740 .
Cole, R.; Sharir, M.; Yap, C. K. (1987). "On $k$ -hulls and related problems". SIAM Journal on Computing . 16 (1): 61–77. doi:10.1137/0216005. MR 0873250.
Dey, T. K. (1998). "Improved bounds for planar $k$ -sets and related problems". Discrete & Computational Geometry . 19 (3): 373–382. doi: 10.1007/PL00009354 . MR 1608878.
Edelsbrunner, H.; Welzl, E. (1986). "Constructing belts in two-dimensional arrangements with applications". SIAM Journal on Computing . 15 (1): 271–284. doi:10.1137/0215019.
Eppstein, D. (1998). "Geometric lower bounds for parametric matroid optimization" (PDF). Discrete & Computational Geometry . 20 (4): 463–476. doi: 10.1007/PL00009396 .
Eppstein, David (August 2022). "A stronger lower bound on parametric minimum spanning trees". Algorithmica. arXiv: 2105.05371 . doi: 10.1007/s00453-022-01024-9 .
Erdős, P.; Lovász, L.; Simmons, A.; Straus, E. G. (1973). "Dissection graphs of planar point sets". A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). Amsterdam: North-Holland. pp. 139–149. MR 0363986.
Fernández-Baca, D.; Slutzki, G.; Eppstein, D. (1996). "Using sparsification for parametric minimum spanning tree problems". Nordic Journal of Computing . 3 (4): 352–366.
Gusfield, D. (1980). Sensitivity analysis for combinatorial optimization. Tech. Rep. UCB/ERL M80/22. University of California, Berkeley.
Hassin, R.; Tamir, A. (1989). "Maximizing classes of two-parametric objectives over matroids". Mathematics of Operations Research . 14 (2): 362–375. doi:10.1287/moor.14.2.362.
Ishii, H.; Shiode, S.; Nishida, T. (1981). "Stochastic spanning tree problem". Discrete Applied Mathematics . 3 (4): 263–273. doi: 10.1016/0166-218X(81)90004-4 .
Katoh, N.; Ibaraki, T. (1983). On the total number of pivots required for certain parametric combinatorial optimization problems. Working Paper 71. Inst. Econ. Res., Kobe Univ. of Commerce.
Lee, Der-Tsai (1982). "On $k$ -nearest neighbor Voronoi diagrams in the plane". IEEE Transactions on Computers. 31 (6): 478–487. doi:10.1109/TC.1982.1676031.
Lovász, L. (1971). "On the number of halving lines". Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica. 14: 107–108.
Matoušek, J. (1990). "Construction of $ε$ -nets". Discrete & Computational Geometry . 5 (5): 427–448. doi: 10.1007/BF02187804 . MR 1064574.
Matoušek, J. (1991). "Approximate levels in line arrangements". SIAM Journal on Computing . 20 (2): 222–227. doi:10.1137/0220013.
Sharir, M.; Smorodinsky, S.; Tardos, G. (2001). "An improved bound for $k$ -sets in three dimensions". Discrete & Computational Geometry . 26 (2): 195–204. doi: 10.1007/s00454-001-0005-3 .
Tóth, G. (2001). "Point sets with many $k$ -sets". Discrete & Computational Geometry . 26 (2): 187–194. doi: 10.1007/s004540010022 .

External links

Halving lines and $k$ -sets, Jeff Erickson
The Open Problems Project, Problem 7: $k$ -sets

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Agarwal, Aronov & Sharir (1997); Chan (2003); Chan (2005a); Chan (2005b).

[2] Chazelle & Preparata (1986); Cole, Sharir & Yap (1987); Edelsbrunner & Welzl (1986).

[FOOTNOTELovász1971-3] Lovász 1971.

[FOOTNOTEErdősLovászSimmonsStraus1973-4] Erdős et al. 1973.

[FOOTNOTEDey1998-5] Dey 1998.

[FOOTNOTETóth2001-6] Tóth 2001.

[FOOTNOTESharirSmorodinskyTardos2001-7] Sharir, Smorodinsky & Tardos 2001.

[8] Lee (1982); Clarkson & Shor (1989).

[FOOTNOTEAlonGyőri1986-9] Alon & Győri 1986.

[FOOTNOTEClarksonShor1989-10] Clarkson & Shor 1989.

[FOOTNOTEEdelsbrunnerWelzl1986-11] Edelsbrunner & Welzl 1986.

[FOOTNOTEChan1999-12] Chan 1999.

[13] Agarwal (1990); Matoušek (1990); Matoušek (1991).

[14] Gusfield (1980); Ishii, Shiode & Nishida (1981); Katoh & Ibaraki (1983); Hassin & Tamir (1989); Fernández-Baca, Slutzki & Eppstein (1996); Chan (2005c).

[FOOTNOTEEppstein2022-15] Eppstein 2022.

[FOOTNOTEEppstein1998-16] Eppstein 1998.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]