Bounding points by lines

Question

Take a set of N points where no group of points with more than two points can be co-linear. The points also lie in the plane. What is the minimum amount of straight lines it takes to bound each point into a separate region so that no two points share the same region? Does the position of the points matter given that they are not co-linear?

Note: 1. Lines may intersect each other but may not intersect any of the N points 2. Define "Bound" to mean each point is in separate region and that region has a finite area.

For example: two points can be bounded by drawing a triangle around both points them drawing one line to separate the triangle into two halves.

Answer 1

As a partial answer: we can always use about $\frac34n$ lines. (We need $\frac34n -1$ when $n$ is divisible by $4$, but slightly more or fewer in other cases.) This assumes we don't care whether the regions are finite or infinite; as mentioned in the comments, if you want all regions to be finite, we can just use $3$ more lines at the beginning to draw a really really big triangle around all $n$ points.

First, we can divide the $n$ points into $\frac12n$ pairs with about $\frac12n$ lines. Without loss of generality, assume the points have distinct $x$-coordinates $x_1, x_2, \dots, x_n$. Then we can draw vertical lines at $x$-coordinates $\frac{x_2+x_3}{2}$, $\frac{x_4+x_5}{2}$, and so on, separating the two leftmost points from the next two from the next two and so on. The result is a picture like this one:

Now take these pairs two at a time. The key is that we can separate two pairs of points with one line. If we need to separate $A$ from $B$, and $C$ from $D$, draw a line through the midpoint of $AB$ and the midpoint of $CD$. For example, to separate the two leftmost pairs of points, we can draw the following line:

(In this case, the line happens to also separate the third pair of points, but that's not guaranteed in general.)

Since there are $\frac12n$ pairs that need to be separated, this can be done with $\frac14n$ more lines, for a total of about $\frac34n$.

---

In the best case, we can use $O(\sqrt n)$ lines, since $k$ lines in general position form $O(k^2)$ regions. But I don't know when that is achievable.

Answer 2

As per Mike Earnest argument in the comments, there are scenarios in which you need $\lceil n / 2 \rceil$ lines:

If the given points all lie on the same circle, dividing that circle into $n$ arcs, then each line can only cross two arcs, so at least $n/2$ lines are necessary. (If any arc is uncrossed, then the two points at the end are not separated).

Now I shall show that $\lceil n/2\rceil$ lines are always sufficient. Firstly, find a single line that cuts all points in half. Color one half of these points blue and the other red.

Now consider the remaining points as a cluster. We can draw a convex hull around this cluster of points. Since there is a line separating the blue from the red points (neither can 'surround' the other) there must be a point where the convex hull switches from red points to blue points.

Choose one red and one blue point from this convex hull that are adjacent, and slice them off our cluster with a line crossing them shifted by an epsilon in the direction of the cluster. Only exactly these two points will be separated off from our remaining cluster by this line.

We can repeatedly do this (calculating new convex hulls) until we are left with two or one points in our cluster, in which case we are done.

---

The above assumes infinite regions. We can at most draw three additional lines around the above construction to get finite regions.

Answer 3

Possible lower bound:

Start with drawing a triangle around the entire set of points, giving us 3 lines. then we will define any line drawn that does not isolate any point to its own region after drawing that one line to be a dividing line denoted D. Any line that happens to isolate a point to a bounded region will be a splitting line S. I believe that the amount of splitting lines S is, S=ceiling(((N/(D+1))-1), meaning the number of lines drawn to bound the points would be

3+D+ceiling(((N/(D+1))-1)=B(Where B is the number of bounding lines)

I want to minimize this value B

First I get rid of the ceiling function and get 3+D+((N/(D=1))-1=B2, where b2 is less than or equal to B

Then I used calculus of variations to figure that D must be equal to sqrt(N)-1

Plugging this in i get that 1+2*sqrt(N)=B2

because b2 is less than or equal to B i put a ceiling function on my answer to get a lower bound of: ceiling(1+2*sqrt(n))