Let be a set of points with no three collinear. For even , a halving pair consists of two points of whose line leaves exactly other points in each open halfplane. Write for the number of unordered halving pairs. The halving-line problem asks for the largest possible value of at a given . Call generic if its first coordinates are distinct, its determined slopes are distinct, and no proper intersection of two segments joining its points lies on a third such segment. For a generic configuration and an integer , the sweep at rank increases the slope from to and, away from the determined slopes, marks the points with smallest . A switch is an exchange of one marked point for one unmarked point. Write for the total number of switches in this sweep. A -set of is a -point subset strictly separable from the remaining points by a line.
Dey proved the upper bound . Tóth constructed configurations with halving pairs.
The preprint proves that there are absolute constants , and such that for every even . The preprint also proves that there are absolute constants and such that for every generic -point configuration with and every integer . For some absolute , the preprint further derives the bound for the number of -sets when , a corollary not contained in the Lean library.
The Lean library is the reference for the results on these pages because Lean has checked every result of the Lean library. Each result is stated as the Lean library states it and is linked to the Lean declaration behind it. Where the preprint states a result differently, the Lean library’s statement is given with the preprint’s beside it. The preprint is a guide only, giving the results their order and names.
HalvingLines is a Lean library: 24 items, in eight groups. Each has a page written by OctoInform, listed below.
No item matches.