wu :: forums
« wu :: forums - Constructive Plane Division by Lines »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 12:02pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: SMQ, william wu, towr, Icarus, ThudnBlunder, Grimbal, Eigenray)
   Constructive Plane Division by Lines
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Constructive Plane Division by Lines  (Read 3171 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Constructive Plane Division by Lines  
« on: Apr 22nd, 2012, 1:08am »
Quote Quote Modify 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: female
Posts: 9
Re: Constructive Plane Division by Lines  
« Reply #1 on: Apr 22nd, 2012, 2:09pm »
Quote Quote Modify 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: male
Posts: 13730
Re: Constructive Plane Division by Lines  
« Reply #2 on: Apr 22nd, 2012, 10:34pm »
Quote Quote Modify 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: male
Posts: 7526
Re: Constructive Plane Division by Lines  
« Reply #3 on: Apr 25th, 2012, 7:19am »
Quote Quote Modify 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: male
Posts: 13730
Re: Constructive Plane Division by Lines  
« Reply #4 on: Apr 25th, 2012, 8:41am »
Quote Quote Modify 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: male
Posts: 2276
Re: Constructive Plane Division by Lines  
« Reply #5 on: Apr 30th, 2012, 9:52am »
Quote Quote Modify 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: male
Posts: 7526
Re: Constructive Plane Division by Lines  
« Reply #6 on: May 16th, 2012, 9:35am »
Quote Quote Modify 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: male
Posts: 13730
Re: Constructive Plane Division by Lines  
« Reply #7 on: May 16th, 2012, 10:16am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board