2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ I agree the statement is not as clear as it could be. For one thing, it explains that "general position" means no three lines through the same point, but it doesn't mention that no two lines can be parallel (which I believe is also intended by "general position"). And they could have said "some number of" instead of $k$, so the use of that symbol was unnecessary. $\endgroup$ – David K Apr 1 at 13:29
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.