Author |
Topic: Constructive Plane Division by Lines (Read 3197 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Constructive Plane Division by Lines
« on: Apr 22nd, 2012, 1:08am » |
 Quote  Modify
|
The following problem is well known and not particularly difficult: into how many regions N lines can divide a plane?
The more difficult problem is to give an actual construction of those N lines. That is: give an algorithm to produce N equations of lines that divide the plane in as many regions as possble.
How does your algoritm change, if the plane is substituted by a given square?
|
|
 IP Logged |
|
|
|
MacNCheese
Newbie
Gender: 
Posts: 9
|
|
Re: Constructive Plane Division by Lines
« Reply #1 on: Apr 22nd, 2012, 2:09pm » |
Quote Modify
|
1 + n(n+1)/2 regions? Make each new line intersect all the previous lines such that no point of intersection has more than 2 lines passing through
And if the above is true, then the algorithm could be:
Lines are given by:
y = n*(x-n) (n varies from 1 to N).
And just scale n by some factor to make them all fit inside a square.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Constructive Plane Division by Lines
« Reply #2 on: Apr 22nd, 2012, 10:34pm » |
Quote Modify
|
When I draw it, I usually use the lines
x=0 and y = (N-1 -k)*(1-x/k), k=1..N-1 (i.e. drawing lines between points (0,k) and (N-1 - k, 0) )
All intersections lie in the triangle (0, 0), (0, N-1), (N-1, 0), so just transform it however you want; scaling, flipping, rotate transposing, so it fits (with a slight border) in your square.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Constructive Plane Division by Lines
« Reply #3 on: Apr 25th, 2012, 7:19am » |
Quote Modify
|
It seems to me that any N lines where no 2 are parallel divide the plane in N(N+1)/2+1 regions.
If you have a square, you just need to scale it down so that all intersection fit within it.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Constructive Plane Division by Lines
« Reply #4 on: Apr 25th, 2012, 8:41am » |
Quote Modify
|
on Apr 25th, 2012, 7:19am, Grimbal wrote:| It seems to me that any N lines where no 2 are parallel divide the plane in N(N+1)/2+1 regions. |
|
Only if no three lines cross in the same point.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Constructive Plane Division by Lines
« Reply #5 on: Apr 30th, 2012, 9:52am » |
Quote Modify
|
on Apr 25th, 2012, 8:41am, towr wrote:
Only if no three lines cross in the same point.
|
|
Exactly! And that's the interesting part.
Solutions presented by MacNCheese & towr make use of the properties of Vandermonde matrix.
Nicely done!
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Constructive Plane Division by Lines
« Reply #6 on: May 16th, 2012, 9:35am » |
Quote Modify
|
on Apr 25th, 2012, 8:41am, towr wrote:
Only if no three lines cross in the same point.
|
|
OK, yes, you also have to avoid multiple intersections. But that is easy to avoid. With random lines, the probability that it happens is zero.
My point was that you don't need to find a clever arrangement of lines. Just avoid parallels and multiple crossings.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Constructive Plane Division by Lines
« Reply #7 on: May 16th, 2012, 10:16am » |
Quote Modify
|
A clever arrangement is useful so you know where the intersections are without having to look for them, and thus how to scale it to fit a given square
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print