wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Constructive Plane Division by Lines
        
(Message started by: Barukh on Apr 22^nd, 2012, 1:08am)

Title: Constructive Plane Division by Lines
Post by Barukh on Apr 22^nd, 2012, 1:08am

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?

Title: Re: Constructive Plane Division by Lines
Post by MacNCheese on Apr 22^nd, 2012, 2:09pm

[hide]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[/hide]

And if the above is true, then the algorithm could be:

[hide]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.
[/hide]

Title: Re: Constructive Plane Division by Lines
Post by towr on Apr 22^nd, 2012, 10:34pm

When I draw it, I usually use the lines
[hide]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.[/hide]

Title: Re: Constructive Plane Division by Lines
Post by Grimbal on Apr 25^th, 2012, 7:19am

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.

Title: Re: Constructive Plane Division by Lines
Post by towr on Apr 25^th, 2012, 8:41am

on 04/25/12 at 07:19:18, 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.

Title: Re: Constructive Plane Division by Lines
Post by Barukh on Apr 30^th, 2012, 9:52am

on 04/25/12 at 08:41:28, 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 [hide]the properties of Vandermonde matrix.[/hide]

Nicely done!

Title: Re: Constructive Plane Division by Lines
Post by Grimbal on May 16^th, 2012, 9:35am

on 04/25/12 at 08:41:28, 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.

Title: Re: Constructive Plane Division by Lines
Post by towr on May 16^th, 2012, 10:16am

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