The stretched geometry of ceilings

The ceiling function rounds numbers up to a not-smaller integer; it is denoted by surrounding its argument by the \lceil and \rceil symbols in LaTeX, ⌈ and ⌉ in html, or ⌈ and ⌉ in unicode. They look sort of like the top halves of square brackets. By analogy to the shape of these symbols, let's call a curve formed from two rays with a common apex, one vertically downwards and the other horizontal in either direction, a ceiling. Geometrically, ceilings behave a lot like lines, and with care this analogy can be made precise.

If a collection of ceilings is in general position (no two rays on the same line) then it is a (weak) pseudoline arrangement: each curve is topologically equivalent to a line, and each two curves are either disjoint or intersect in a single crossing point. And if a collection of points is in general position (no two having the same \( x \)-coordinate or the same \( y \)-coordinate) then each two points determine a unique ceiling, which does not pass through any other of the points. Just as a non-vertical line divides a set of points into an upper and lower halfspace, so does a ceiling: the lower halfspace is the set of points below the horizontal ray of the ceiling, and the upper halfspace is everything else. So in their basic combinatorial properties, ceilings already behave much like lines.

But more strongly, suppose \( S \) is a set of \( n \) points \( s_1,s_2,s_3,\dots \) in general position. Then it turns out that there exists a set \( T \) of \( n \) points \( t_1,t_2,t_3,\dots \) (no three collinear) with the following property: for every \( i, \) \( j, \) and \( k, \) point \( s_i \) is above the ceiling through \( s_j \) and \( s_k \) if and only if point \( t_i \) is above the line through \( t_j \) and \( t_k. \) That is, the lines through pairs of points in \( T \) partition the points in exactly the same way that the ceilings through pairs of points in \( S \) do. Two line segments or ceiling segments cross if and only if each of them separates the endpoints of the other one, so the crossings of segments in \( T \) are also exactly the same as the crossings of segments in \( S. \)

There's more than one way of finding \( T, \) but I think one of the simplest is a stretching transformation that I first encountered in a paper on weak epsilon-nets by Bukh, Matoušek, and Nivasch, and that Tóth and Fulek and my coauthors and I borrowed for our papers on universal point sets. If we move the points in \( S \) without changing their coordinatewise sorted order, nothing changes, so we can replace their coordinates by their positions in the sorted order, after which their coordinates are in the range from \( 0 \) to \( n-1 \). Then, the point in \( T \) corresponding to the point \( (x,y) \) in \( S \) is simply \( (x,n^y). \) The key property that makes it work is that this vertical expansion is large enough so that, for each point, the radial order of the points below it is the same as their sorted order by their \( x \)-coordinates.

I was thinking about this again after seeing a paper, "Discrete Geometry on Red and Blue Points in the Plane Lattice", by Mikio Kano and Kazuhiro Suzuki, in János Pach's recent book Thirty Essays on Geometric Graph Theory. Kano and Suzuki's paper is about the existence of certain sets axis-parallel polygonal paths with at most one bend (a generalization of segments of ceilings, also including floors and axis-parallel line segments) analogous to known properties of line segments. Their generalization is a little messier because it allows two paths between any two points, but if we use ceilings and stretchings everything becomes easy. Some examples:

The ham sandwich theorem

For every two sets of points (whose union has no three collinear points) there exists a line (the ham sandwich cut) that bisects both sets (meaning that it has equal numbers of points from the set on each of its sides, and possibly passes through one of the points). Corollary by stretching: for every two sets of points (whose union is in general position) there exists a ceiling that bisects both sets. (To show this, you have to unstretch the ham sandwich line, which you can do by shifting it until it touches exactly two points, then in the unstretched point set finding the ceiling through those two points and reversing the shift.)

Red-blue matching

For every set of \( n \) red and \( n \) blue points (no three collinear) there exists a set of \( n \) disjoint line segments each having one red and one blue endpoint. Proof idea: Apply the ham sandwich theorem and recurse on each side. Corollary by stretching (one of Kano and Suzuki's main results): for every set of \( n \) red and \( n \) blue points in general position there exists a set of \( n \) disjoint ceiling segments each having one red and one blue endpoint.

Convex hulls

By Carathéodory's theorem, the intersection of the halfspaces that contain a point set \( S \) is the same shape as the union of the triangles described by triples of the points; this shape is the convex hull of \( S, \) and it consists of the points that cannot be separated from \( S \) by a line. As Csaba Tóth pointed out in his WADS 2013 talk, the shape bounded by the ceilings through three points is not a triangle but a rectangle, extending in the \( x \) direction between the \( x \)-coordinates of the bottom two points and extending in the \( y \) direction between the \( y \)-coordinates of the top two points; it is connected to the bottom point (and possibly also the top point) by axis-parallel line segments outside of these ranges. Thus, we have as a corollary by stretching: The intersection of the sides of ceilings that contain a point set \( S \) is the same shape as the union of rectangles (plus connecting segments) described by triples of the points; this shape consists of the points that cannot be separated from \( S \) by a ceiling. The ceiling hull of a point set is a little strange looking: on top it is like the bounding box of the points, but on the bottom it is instead like the orthogonal convex hull.

Centerpoints

For every set \( S \) of \( n \) points (no three collinear) there exists another point \( c \) (the centerpoint, not necessarily belonging to \( S) \) such that every line through \( c \) contains at least \( n/3 \) of the points on each of the closed halfplanes it bounds. Proof idea: Use Helly's theorem on the family of halfplanes containing at least \( n/3 \) points. Corollary by stretching: For every set of \( n \) points in general position there exists another point \( c \) such that every ceiling through \( c \) has at least \( n/3 \) points on each of its (topologically closed) sides. There's a simpler proof and construction in this case: just find a point \( c \) such that the halfplane above it and the two quarterplanes below on either side each contain at least \( n/3 \) points of \( S. \)

Halving lines

For every set \( S \) of \( n \) points in the plane (no three collinear, \( n \) even) there exist at most \( O(n^{4/3}) \) distinct ways of bisecting the points by a line [Dey 1998]. Corollary by stretching: For every set \( S \) of \( n \) points in the plane (in general position, \( n \) even) there exist at most \( O(n^{4/3}) \) distinct ways of bisecting the points by a ceiling. But actually this is a bit of a trick problem: the number of halving ceilings (for evenly many points) is at most \( n-1, \) because each vertical line contains the vertical ray of exactly one halving ceiling (up to combinatorial equivalence), two vertical lines form different halving ceilings only when they are separated by a point in \( S, \) the two vertical lines on either side of the topmost point give the same split, and the two vertical lines to the left and right of all the points give the same split. The example below shows that this \( n-1 \) bound is tight.

It's tempting to try to use stretching to solve Conjecture 10 of Kano and Suzuki, that every set of \( n \) points is in general position is universal for drawings of trees with maximum degree three using L-shaped edges. For the corresponding line segment problem, every set of \( n \) points (no three collinear) is universal for a much larger set of graphs, the outerplanar graphs. But unfortunately this result doesn't translate to ceilings, because two ceilings with the same endpoint could overlap, spoiling the drawing.

---

Comments: