3
$\begingroup$

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.

$\endgroup$
18
  • $\begingroup$ If they are in a circle they can still be separated by $n-1$ lines as in the case where they are all co-linear. $\endgroup$
    – John Douma
    Aug 9, 2019 at 18:29
  • $\begingroup$ I deleted my answer, I underestimated the question. It's easy to show $n - 1$ lines are always sufficient regardless of collinearity, which what my answer did, but that's not sufficient. Can we always do with less assuming non-collinearity? $\endgroup$
    – orlp
    Aug 9, 2019 at 18:37
  • $\begingroup$ I want to try to keep each points region finitely bounded by a region with finite area so i don't believe n-1 will work $\endgroup$
    – Rdog60
    Aug 9, 2019 at 18:41
  • $\begingroup$ I don't think your answer is as interesting with finite area. You can always make the area finite by drawing a triangle around it - the fundamental question is for the infinite plane. $\endgroup$
    – orlp
    Aug 9, 2019 at 18:41
  • $\begingroup$ if you use the ceiling(log2(N)) plus 3 for a triangle approach it is not correct $\endgroup$
    – Rdog60
    Aug 9, 2019 at 18:44

3 Answers 3

1
$\begingroup$

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:

enter image description here

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:

enter image description here

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

$\endgroup$
7
  • $\begingroup$ can you explain the n/2 pairs with n/2 lines part to me? $\endgroup$
    – Rdog60
    Aug 9, 2019 at 19:10
  • $\begingroup$ I've added illustrations. Do they help? $\endgroup$ Aug 9, 2019 at 19:20
  • $\begingroup$ The picture you drew didn't finitely bound each point to a finite area though? or am I still confused? $\endgroup$
    – Rdog60
    Aug 9, 2019 at 19:23
  • $\begingroup$ @Rdog60 For that, just draw a really really big triangle around the whole thing. All your existing regions become finite when you do that. $\endgroup$ Aug 9, 2019 at 19:24
  • $\begingroup$ Thats what I was thinking, I could use your approximation and add 3 right? $\endgroup$
    – Rdog60
    Aug 9, 2019 at 19:30
1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Nice solution! As delicious as it is, the full power of the ham sandwich theorem is not needed here. $\tag*{}$ Consider the convex hull of the points. Each vertex of this hull is a given point, so is either red or blue. Some segment of the hull connects a red point to a blue point. Taking that line, and shifting it a tiny bit towards the other points, gives a line which separates one red and one blue point from the rest. Now ignore those two points, and lather/rinse/repeat on the rest. $\endgroup$ Aug 9, 2019 at 20:11
  • $\begingroup$ @MikeEarnest I've improved my answer with your convex hull idea. $\endgroup$
    – orlp
    Aug 9, 2019 at 20:23
  • $\begingroup$ So to clarify, 2n/3 is an upper bound on the number of lines needed? $\endgroup$
    – Rdog60
    Aug 9, 2019 at 20:27
  • $\begingroup$ @Rdog60 No, it's $n/2$ now, my idea got improved by Mike Earnest. $\endgroup$
    – orlp
    Aug 9, 2019 at 20:28
  • $\begingroup$ I think I may have a lower bound but it is a little wacky $\endgroup$
    – Rdog60
    Aug 9, 2019 at 20:34
0
$\begingroup$

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))

$\endgroup$
3
  • $\begingroup$ Does this work at all? $\endgroup$
    – Rdog60
    Aug 9, 2019 at 20:42
  • $\begingroup$ I do not see why the number of splitting lines must be $\lceil \frac{N}{D+1}-1\rceil$. Also, the true lower bound is $\approx \sqrt{2n}$, so it cannot be $2\sqrt n$ as you have. $\endgroup$ Aug 9, 2019 at 23:31
  • $\begingroup$ Proof of last comment: any $k$ lines, with no two parallel and no three meeting at one point, divide the plane into $(k^2+k+2)/2$ regions (see here). Draw $k$ lines, and place a point in each region, then surround the points with a triangle. This means $k+3$ lines sufficed for $n=(k^2+k+2)/2$ points. Solving for $k+3$ in terms of $n$, you get $k = \frac12 (\sqrt{8 n - 7} - 1)+3\approx \sqrt{2n}$. $\endgroup$ Aug 9, 2019 at 23:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .