Interpreting a problem in combinatorial geometry

179 Views Asked by At

Problem: Let $L$ be a set of $n$ lines in the plane in general position, that is, no three of them containing the same point. The lines of $L$ cut the plane into $k$ regions. Prove by induction on $n$ that this subdivision of the plane has $\binom{n}{2}$ vertices, $n^2$ edges, and $\binom{n}{2} + n + 1$ cells.

I don't need help solving this problem, I just need help interpreting it. What does it mean that the plane is cut into $k$ regions? I thought that the number of regions was determined by $n$. Also, what's the point of the $k$ if we're not proving anything about it?

Finally, what is meant by cells? Also, are edges the finite segments between intersections?

2

There are 2 best solutions below

0
On

I tried the case for $n=3$ and I think i found the correct interpretation, but you should do it yourself to confirm. It seems that they do not allow for parallel lines, in which case you are right that the $k$ in "$k$ regions" is not relevant.

"Vertices" is clear: a vertex is a point where a pair of lines intersect

"Edges" are any piece of line: a finite line segment between vertices, an infinite ray emanating from a vertex, or a whole line (in the case of $n=1$)

"Cells" means any face created by the lines. In other words, a region of the plane is a cell if you can draw a continuous path between any 2 points in the cell without crossing a line

0
On

For the statement to be correct, no two lines may be parallel. The symbol $k$ has no significance whatsoever, and might as well be omitted; the question would have been clearer if it said

The lines of $L$ cut the plane into some number of regions.

The question is also poorly phrased as it does not specify what the words "vertices", "edges", "regions" and "cells" mean. Judging from the given formulas, my best guess is the following:

A vertex is a point of intersection of two lines. Denote the set of vertices by $V$: $$V:=\{l\cap m:\ l,m\in L\}.$$

The vertices partition the lines into segments; these are the edges. Note that some are bounded and some are unbounded. More precisely, the set of edges is the set of connected components of $(\bigcup L)-V$.

Similarly, omitting the lines from the plane leaves a number of regions, and again some are bounded and some are unbounded. The cells are the bounded regions. More precisely, the set of regions is the set of connected components of $P-\bigcup L$, where $P$ denotes the plane, and the set of cells is the subset of bounded connected components of $P-\bigcup L$.