Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #39375

Re: Fiting squares under a curve.

Show key headers only | View raw

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Thursday, 16 September 2021 at 00:33:23 UTC+1, Ben Bacarisse wrote:

>> So let me check a few cases. For f(x) = 1 the only perfect solution has 
>> N = 2 and the x_i being just [0,1]. If N is given and > 2, then the 
>> best solution is to pack the internal x_i (0 < i < N) as close to 0 or 1 
>> as possible. 
>>
> If the f(x) is square, then the problem is easy and the answer is to
> fit a single 1x1 square under the curve.  If you say that N must be
> greater than 2, then if you set all the squares except 1 to tiny
> values, you've got effectively one square left which accounts for all
> the area. But the tiny squares would be horribly distorted, so this
> isn't actually a usable solution. That's why N can't be fixed.
>>
>> And for f(x) = 1/2 the optimum solution has N = 3 and the x_i at [0, 
>> 1/2, 1]. Again, for N > 3, packing the extra points close to 0, 1/2 or 
>> 1 seems optimal. 
>> 
> Yes f(x) = 1/2 is again easy. Fit two squares. If you insist that N be greater
> than 3, you have the problem outlined before again. The tiny squares are
> horribly distorted when the assembled frieze is stretched out over the
> wall. So this might not be a usable solution.
>>
>> For f(x) = x, I don't know the best N, but for N = 3 the optimum 
>> solution is (I think) [0, 1/3, 1] with an error of 5/90. I don't think 
>> that can be beaten for larger N, but I've not played around with it 
>> much. 
>>
> This is the real case, and I haven't worked it out. For N = 3, and f(x) = x,
> the error function has a low point at [0, 1/3, 1], and is U-shaped.
> For N = 4, an exhaustive search shows that the optimum solution is
> [0, 1/9, 1/3, 1.0] with an error of 0.0094. In other words, you keep
> the big square as it is, and sub-divide the smaller one.

I don't get the same error values so I am not 100% I'm doing the right
thing:

  *Main> error_of_i int_id [0, 1/3, 1]
  5.5555555555555663e-2
  *Main> error_of_i int_id [0, 1/9, 1/3, 1]
  6.17283950617295e-3

For simplicity, I pass the integral of f into the function.  int_id is
the integral of f(x) = x:

  int_id x = x**2 / 2

But the progression above immediately suggests we should try:

  *Main> error_of_i int_id [0, 1/27, 1/9, 1/3, 1]
  6.858710562415376e-4

which is indeed a better fit, and we can get the error down to close to
the limit of floating point accuracy by adding more inverse powers:

  powers p n = 0 : reverse (take n $ iterate (*p) 1)
  *Main> error_of_i int_id (powers (1/3) 35)
  1.1103597431229582e-16

So I would guess that the (theoretical) optimum is an infinite set of
points with an error of 0.  In your practical case, you'd add points
until you got to within one pixel of 0.

My Haskell code is:

  error_of_i i points =
    if all (uncurry (<)) intervals
    then sum $ map area_diff intervals
    else error "Points not in order"
    where intervals = zipWith (,) points (tail points)
          area_diff (a,b) = abs((i b - i a) - (b - a)^2)

> Thanks for taking the time to look at it.

You are welcome.  I like a curious problem.

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-15 06:59 -0700
  Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-15 15:17 +0100
    Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-15 08:06 -0700
      Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-15 22:33 +0100
        Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-15 15:01 -0700
          Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-16 00:33 +0100
            Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-17 03:25 -0700
              Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-17 14:22 +0100
                Re: Fiting squares under a curve. Andy Walker <anw@cuboid.co.uk> - 2021-09-17 16:25 +0100
                Re: Fiting squares under a curve. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-17 20:59 +0100
                Re: Fiting squares under a curve. Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-23 02:14 -0700

csiph-web