Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
K-set (geometry)
Résumé
In discrete geometry, a -set of a finite point set in the Euclidean plane is a subset of elements of that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a -set of a finite point set is a subset of elements that can be separated from the remaining points by a hyperplane. In particular, when (where is the size of ), the line or hyperplane that separates a -set from the rest of is a halving line or halving plane.
The -sets of a set of points in the plane are related by projective duality to the -levels in an arrangement of lines. The -level in an arrangement of lines in the plane is the curve consisting of the points that lie on one of the lines and have exactly lines below them. Discrete and computational geometers have also studied levels in arrangements of more general kinds of curves and surfaces.
It is of importance in the analysis of geometric algorithms to bound the number of -sets of a planar point set, or equivalently the number of -levels of a planar line arrangement, a problem first studied by Lovász and Erdős et al. The best known upper bound for this problem is , as was shown by Tamal Dey 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 for some constant , as shown by Tóth.
In three dimensions, the best upper bound known is , and the best lower bound known is .
For points in three dimensions that are in convex position, that is, are the vertices of some convex polytope, the number of -sets is
which follows from arguments used for bounding the complexity of th order Voronoi diagrams.
For the case when (halving lines), the maximum number of combinatorially distinct lines through two points of that bisect the remaining points when is
Bounds have also been proven on the number of -sets, where a -set is a -set for some . In two dimensions, the maximum number of -sets is exactly , while in dimensions the bound is .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.