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

Groups > comp.theory > #39364 > unrolled thread

Fiting squares under a curve.

Back to article view | Back to comp.theory

Contents

  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

#39364 — Fiting squares under a curve.

Maybe there's enough theoretical content here to justify a post to comp.theory, though it's largely a practical problem.

I have an image made up of a frieze of square cells. I can add cells at will to the left or the rich (within reason). I want to fit it to a wall with a curved top, retaining the aspect ratio as much as possible. So small cells in low parts of the wall, large cells in high parts.

The flat top case is easy. The cell width is given by the height of the wall to make a square.  It is then rounded to make a whole number of cells. As long as the wall is longer than it is high, the worst case is a 150% scaling in the x direction. Normally the wall is much longer than high, and distortion is negligible.

However I want to allow a curved top. So the cells are no longer of the same height, in fact they are quads with two right angles at the bottom and a sloping top. The stright line function of the cell tops approximates the wall top curve.

if we consider the solution to be a set of points in x along the wall representing cells, and the midpints the boundaries of cells, then we 
need to minimise the function

sum over each cell : integral of wall function from cell x low to cell x high minus (cell x high - cell x low) squared.

Is there a fast way of doing this? 

[toc] | [next] | [standalone]

#39365

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

> Maybe there's enough theoretical content here to justify a post to
> comp.theory, though it's largely a practical problem.
>
> I have an image made up of a frieze of square cells. I can add cells
> at will to the left or the rich (within reason). I want to fit it to a
> wall with a curved top, retaining the aspect ratio as much as
> possible. So small cells in low parts of the wall, large cells in high
> parts.
>
> The flat top case is easy. The cell width is given by the height of
> the wall to make a square.  It is then rounded to make a whole number
> of cells. As long as the wall is longer than it is high, the worst
> case is a 150% scaling in the x direction. Normally the wall is much
> longer than high, and distortion is negligible.
>
> However I want to allow a curved top. So the cells are no longer of
> the same height, in fact they are quads with two right angles at the
> bottom and a sloping top. The stright line function of the cell tops
> approximates the wall top curve.
>
> if we consider the solution to be a set of points in x along the wall
> representing cells, and the midpints the boundaries of cells, then we
> need to minimise the function
>
> sum over each cell : integral of wall function from cell x low to cell
> x high minus (cell x high - cell x low) squared.
>
> Is there a fast way of doing this? 

It might be useful to know why I didn't comment before in
comp.programming: I didn't understand what the constraints are.

You can add cells to some already given strip of cells but what is "with
reason"?  Can you add cells from some restricted set, or can you choose
everything about the cells you add?  Can you choose anything about the
initial frieze?

You can scale something.  It is the function to be fitted or the frieze
of cells?  Scaling implies an origin.  What is that origin and/or can
the scaling be accompanied by a translation making the origin
unimportant?

Do you have any extra information about the function?  For example, is
it everywhere continuous and maybe even smooth?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#39366

On Wednesday, 15 September 2021 at 15:17:39 UTC+1, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> 
> > Maybe there's enough theoretical content here to justify a post to 
> > comp.theory, though it's largely a practical problem. 
> > 
> > I have an image made up of a frieze of square cells. I can add cells 
> > at will to the left or the rich (within reason). I want to fit it to a 
> > wall with a curved top, retaining the aspect ratio as much as 
> > possible. So small cells in low parts of the wall, large cells in high 
> > parts. 
> > 
> > The flat top case is easy. The cell width is given by the height of 
> > the wall to make a square. It is then rounded to make a whole number 
> > of cells. As long as the wall is longer than it is high, the worst 
> > case is a 150% scaling in the x direction. Normally the wall is much 
> > longer than high, and distortion is negligible. 
> > 
> > However I want to allow a curved top. So the cells are no longer of 
> > the same height, in fact they are quads with two right angles at the 
> > bottom and a sloping top. The stright line function of the cell tops 
> > approximates the wall top curve. 
> > 
> > if we consider the solution to be a set of points in x along the wall 
> > representing cells, and the midpints the boundaries of cells, then we 
> > need to minimise the function 
> > 
> > sum over each cell : integral of wall function from cell x low to cell 
> > x high minus (cell x high - cell x low) squared. 
> > 
> > Is there a fast way of doing this?
> It might be useful to know why I didn't comment before in 
> comp.programming: I didn't understand what the constraints are. 
> 
> You can add cells to some already given strip of cells but what is "with 
> reason"? Can you add cells from some restricted set, or can you choose 
> everything about the cells you add? Can you choose anything about the 
> initial frieze? 
>
The user specifies the contents of the cell, which can be any image. In fact
it's a vector image. I then construct a frieze from the cell by adding as many
cells as are needed to make up the length of the wall (in the flat top case).
Often the images will have geometry which joins. So two adjoining cells must 
have a common edge of the same height. I was planning to make the cells
into quads with two ritch angles at the bottom and a slanted top to accommodate
this requirement.
I can add as many cells as I want to the frieze, until I overload the capacity of the
various systems to handle the geometry. Which means about a hundred cells 
would be a limit. There's also no point in having a very tiny cell. The end user can't 
see sub-pixel geometry, it's waste of resources calculating it.
> 
> You can scale something. It is the function to be fitted or the frieze 
> of cells? Scaling implies an origin. What is that origin and/or can 
> the scaling be accompanied by a translation making the origin 
> unimportant? 
> 
I can't scale the wall to the end user. But of course I can scale intermediates,
for instance to trivially transform the rectangular cell problem into the square 
cell problem by strething or contracting the wall. Each cell is small square
image. I was thinking of simply scaling the whole cell by a factor, but of course
this isn't strictly correct - internally different regions of the cell have different
scales because the wall is not flat over the cell. I'm hoping this won't matter
too much visually.
  
> Do you have any extra information about the function? For example, is 
> it everywhere continuous and maybe even smooth? 
> 
The function was chosen to be as close as possible to an existing industry-
standard "variable width profile" which we can manipulate, but the equations 
are not public. The user enters "width points" and drags them out and slides 
them, and the profile interpolates. I ended up using quintic interpolation,
with special cases for when two width points  are at identical x positions.
So you can create steps and straight line sections, but normally the
function is continuous and smooth for its entire length. (I can also
restrict the function as a last resort, I coded it and have control of it, but
then it would no longer be as similar to the function in the industry-
standard tool).

[toc] | [prev] | [next] | [standalone]

#39367

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

> On Wednesday, 15 September 2021 at 15:17:39 UTC+1, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
>> 
>> > Maybe there's enough theoretical content here to justify a post to 
>> > comp.theory, though it's largely a practical problem. 
>> > 
>> > I have an image made up of a frieze of square cells. I can add cells 
>> > at will to the left or the rich (within reason). I want to fit it to a 
>> > wall with a curved top, retaining the aspect ratio as much as 
>> > possible. So small cells in low parts of the wall, large cells in high 
>> > parts. 
>> > 
>> > The flat top case is easy. The cell width is given by the height of 
>> > the wall to make a square. It is then rounded to make a whole number 
>> > of cells. As long as the wall is longer than it is high, the worst 
>> > case is a 150% scaling in the x direction. Normally the wall is much 
>> > longer than high, and distortion is negligible. 
>> > 
>> > However I want to allow a curved top. So the cells are no longer of 
>> > the same height, in fact they are quads with two right angles at the 
>> > bottom and a sloping top. The stright line function of the cell tops 
>> > approximates the wall top curve. 
>> > 
>> > if we consider the solution to be a set of points in x along the wall 
>> > representing cells, and the midpints the boundaries of cells, then we 
>> > need to minimise the function 
>> > 
>> > sum over each cell : integral of wall function from cell x low to cell 
>> > x high minus (cell x high - cell x low) squared. 
>> > 
>> > Is there a fast way of doing this?
>> It might be useful to know why I didn't comment before in 
>> comp.programming: I didn't understand what the constraints are. 
>> 
>> You can add cells to some already given strip of cells but what is "with 
>> reason"? Can you add cells from some restricted set, or can you choose 
>> everything about the cells you add? Can you choose anything about the 
>> initial frieze? 
>>
> The user specifies the contents of the cell, which can be any image. In fact
> it's a vector image. I then construct a frieze from the cell by adding as many
> cells as are needed to make up the length of the wall (in the flat top case).
> Often the images will have geometry which joins. So two adjoining cells must 
> have a common edge of the same height. I was planning to make the cells
> into quads with two ritch angles at the bottom and a slanted top to accommodate
> this requirement.
> I can add as many cells as I want to the frieze, until I overload the capacity of the
> various systems to handle the geometry. Which means about a hundred cells 
> would be a limit. There's also no point in having a very tiny cell. The end user can't 
> see sub-pixel geometry, it's waste of resources calculating it.
>> 
>> You can scale something. It is the function to be fitted or the frieze 
>> of cells? Scaling implies an origin. What is that origin and/or can 
>> the scaling be accompanied by a translation making the origin 
>> unimportant? 
>> 
> I can't scale the wall to the end user. But of course I can scale intermediates,
> for instance to trivially transform the rectangular cell problem into the square 
> cell problem by strething or contracting the wall. Each cell is small square
> image. I was thinking of simply scaling the whole cell by a factor, but of course
> this isn't strictly correct - internally different regions of the cell have different
> scales because the wall is not flat over the cell. I'm hoping this won't matter
> too much visually.
>   
>> Do you have any extra information about the function? For example, is 
>> it everywhere continuous and maybe even smooth? 
>> 
> The function was chosen to be as close as possible to an existing industry-
> standard "variable width profile" which we can manipulate, but the equations 
> are not public. The user enters "width points" and drags them out and slides 
> them, and the profile interpolates. I ended up using quintic interpolation,
> with special cases for when two width points  are at identical x positions.
> So you can create steps and straight line sections, but normally the
> function is continuous and smooth for its entire length. (I can also
> restrict the function as a last resort, I coded it and have control of it, but
> then it would no longer be as similar to the function in the industry-
> standard tool).

I'm sorry but I can't work out what the optimisation problem is from
this description.  Also, the problem is described in domain-specific
jargon which makes it hard for outsiders.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#39369

On Wednesday, 15 September 2021 at 22:33:21 UTC+1, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> 
> > On Wednesday, 15 September 2021 at 15:17:39 UTC+1, Ben Bacarisse wrote: 
> >> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> >> 
> >> > Maybe there's enough theoretical content here to justify a post to 
> >> > comp.theory, though it's largely a practical problem. 
> >> > 
> >> > I have an image made up of a frieze of square cells. I can add cells 
> >> > at will to the left or the rich (within reason). I want to fit it to a 
> >> > wall with a curved top, retaining the aspect ratio as much as 
> >> > possible. So small cells in low parts of the wall, large cells in high 
> >> > parts. 
> >> > 
> >> > The flat top case is easy. The cell width is given by the height of 
> >> > the wall to make a square. It is then rounded to make a whole number 
> >> > of cells. As long as the wall is longer than it is high, the worst 
> >> > case is a 150% scaling in the x direction. Normally the wall is much 
> >> > longer than high, and distortion is negligible. 
> >> > 
> >> > However I want to allow a curved top. So the cells are no longer of 
> >> > the same height, in fact they are quads with two right angles at the 
> >> > bottom and a sloping top. The stright line function of the cell tops 
> >> > approximates the wall top curve. 
> >> > 
> >> > if we consider the solution to be a set of points in x along the wall 
> >> > representing cells, and the midpints the boundaries of cells, then we 
> >> > need to minimise the function 
> >> > 
> >> > sum over each cell : integral of wall function from cell x low to cell 
> >> > x high minus (cell x high - cell x low) squared. 
> >> > 
> >> > Is there a fast way of doing this? 
> >> It might be useful to know why I didn't comment before in 
> >> comp.programming: I didn't understand what the constraints are. 
> >> 
> >> You can add cells to some already given strip of cells but what is "with 
> >> reason"? Can you add cells from some restricted set, or can you choose 
> >> everything about the cells you add? Can you choose anything about the 
> >> initial frieze? 
> >> 
> > The user specifies the contents of the cell, which can be any image. In fact 
> > it's a vector image. I then construct a frieze from the cell by adding as many 
> > cells as are needed to make up the length of the wall (in the flat top case). 
> > Often the images will have geometry which joins. So two adjoining cells must 
> > have a common edge of the same height. I was planning to make the cells 
> > into quads with two ritch angles at the bottom and a slanted top to accommodate 
> > this requirement. 
> > I can add as many cells as I want to the frieze, until I overload the capacity of the 
> > various systems to handle the geometry. Which means about a hundred cells 
> > would be a limit. There's also no point in having a very tiny cell. The end user can't 
> > see sub-pixel geometry, it's waste of resources calculating it. 
> >> 
> >> You can scale something. It is the function to be fitted or the frieze 
> >> of cells? Scaling implies an origin. What is that origin and/or can 
> >> the scaling be accompanied by a translation making the origin 
> >> unimportant? 
> >> 
> > I can't scale the wall to the end user. But of course I can scale intermediates, 
> > for instance to trivially transform the rectangular cell problem into the square 
> > cell problem by strething or contracting the wall. Each cell is small square 
> > image. I was thinking of simply scaling the whole cell by a factor, but of course 
> > this isn't strictly correct - internally different regions of the cell have different 
> > scales because the wall is not flat over the cell. I'm hoping this won't matter 
> > too much visually. 
> > 
> >> Do you have any extra information about the function? For example, is 
> >> it everywhere continuous and maybe even smooth? 
> >> 
> > The function was chosen to be as close as possible to an existing industry- 
> > standard "variable width profile" which we can manipulate, but the equations 
> > are not public. The user enters "width points" and drags them out and slides 
> > them, and the profile interpolates. I ended up using quintic interpolation, 
> > with special cases for when two width points are at identical x positions. 
> > So you can create steps and straight line sections, but normally the 
> > function is continuous and smooth for its entire length. (I can also 
> > restrict the function as a last resort, I coded it and have control of it, but 
> > then it would no longer be as similar to the function in the industry- 
> > standard tool).
> I'm sorry but I can't work out what the optimisation problem is from 
> this description. Also, the problem is described in domain-specific 
> jargon which makes it hard for outsiders. 
> 
OK, lets try a more formal approach.

We have a function f(x) which is defined over x = 0.0 to1.0, and is always non-negative.

We have a set of values x_0 ... x_N, in ascending order. x_0 = 0.0, x_N = 1.0. These
define N-1 non-overlapping intervals.

The integral f(x) from x=0 to x = 1.0 is known to be less than 1.0.

The optimisation problem is to define the set of points such that the sum

for each interval 

| integral f(x) from x_i to x_i+1 - (x_i+1 - x_i)^2 |

is at a minimum.

Additionally, an interval cannot be less than delta_min, which will be 1 pixel, so usually
between 0.01 and 0.001, because the range x = 0 - 1.0 will generally span 100 to 1000
pixels. 

[toc] | [prev] | [next] | [standalone]

#39370

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

> OK, lets try a more formal approach.

That's always my preference...  Thanks.

> We have a function f(x) which is defined over x = 0.0 to 1.0, and is
> always non-negative.
>
> We have a set of values x_0 ... x_N, in ascending order. x_0 = 0.0,
> x_N = 1.0. These define N-1 non-overlapping intervals.

I think you mean you have an N and wish to find the x_i.  If you have
the x_i you can't change anything to minimise the "error" function
you've defined.

But I think you suggested that N was also up for grabs because you
could, within reason, add cells (but I am not 100% sure I know what the
cells correspond to in this version).

> The integral f(x) from x=0 to x = 1.0 is known to be less than 1.0.
>
> The optimisation problem is to define the set of points such that the sum
>
> for each interval 
>
> | integral f(x) from x_i to x_i+1 - (x_i+1 - x_i)^2 |
>
> is at a minimum.

A curious problem.  I can't visualise it well.  I suspect it's hard.

> Additionally, an interval cannot be less than delta_min, which will be
> 1 pixel, so usually between 0.01 and 0.001, because the range x = 0 -
> 1.0 will generally span 100 to 1000 pixels.

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.

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.

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.

Do you agree with these solutions?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#39374

On Thursday, 16 September 2021 at 00:33:23 UTC+1, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes: 
> 
> > OK, lets try a more formal approach.
> That's always my preference... Thanks. 
> 
> > We have a function f(x) which is defined over x = 0.0 to 1.0, and is
> > always non-negative. 
> > 
> > We have a set of values x_0 ... x_N, in ascending order. x_0 = 0.0, 
> > x_N = 1.0. These define N-1 non-overlapping intervals.
> I think you mean you have an N and wish to find the x_i. If you have 
> the x_i you can't change anything to minimise the "error" function 
> you've defined. 
> 
> But I think you suggested that N was also up for grabs because you 
> could, within reason, add cells (but I am not 100% sure I know what the 
> cells correspond to in this version).
>
I expressed that badly. Instead of saying "we have a set of values", I should
have said "we need to find a set of values". Both the values and N are up for
grabs. That's because the intervals correspond to cells in the frieze, and I
can add or remove cells at will.
>
> > The integral f(x) from x=0 to x = 1.0 is known to be less than 1.0. 
> > 
> > The optimisation problem is to define the set of points such that the sum 
> > 
> > for each interval 
> > 
> > | integral f(x) from x_i to x_i+1 - (x_i+1 - x_i)^2 | 
> > 
> > is at a minimum.
> A curious problem. I can't visualise it well. I suspect it's hard.
>
It's cropped up naturally. The problem is to fit the frieze to the wall so that
the aspect ratio is reasonably well preserved between high sections and
low sections. I think trying to fit squares under the curve is the best way to
express that mathematically.

> > Additionally, an interval cannot be less than delta_min, which will be 
> > 1 pixel, so usually between 0.01 and 0.001, because the range x = 0 - 
> > 1.0 will generally span 100 to 1000 pixels.
> 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.
> 
> Do you agree with these solutions? 
> 
Thanks for taking the time to look at it.

[toc] | [prev] | [next] | [standalone]

#39375

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.

[toc] | [prev] | [next] | [standalone]

#39376

On 17/09/2021 14:22, Ben Bacarisse wrote:
>    *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
[...]
> 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, [...]

	I'm still confused by the problem, by Malcolm's description
of it, and by Ben's Haskell!  But in the case f(x) == x, perhaps
worth noting that the situation with N tiles with the last starting
at X consists of the problem with N-1 tiles scaled by a factor X,
together with the last tile.  So the error with N tiles is

   E[N] == X^2 E[N-1] + { error with tile size 1-X between X and 1 } ,

which is more-or-less quadratic in X [somewhat confused by the mod
in the error term], and so can be solved by "easy" calculus/algebra.
If indeed X == 1/3 is correct for all N, then it follows immediately
that the general solution is of form

   [0, ..., 1/81, 1/27, 1/9, 1/3, 1] ,

and each extra tile is taking away 8/9 of the error.  Formal proof
and details left as an exercise ....

-- 
Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Bach,CPE

[toc] | [prev] | [next] | [standalone]

#39383

Andy Walker <anw@cuboid.co.uk> writes:

> On 17/09/2021 14:22, Ben Bacarisse wrote:
>>    *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
> [...]
>> 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, [...]
>
> 	I'm still confused by the problem, by Malcolm's description
> of it, and by Ben's Haskell!  But in the case f(x) == x, perhaps
> worth noting that the situation with N tiles with the last starting
> at X consists of the problem with N-1 tiles scaled by a factor X,
> together with the last tile.

That's a good observation.  I was too caught up in investigating
numerical solutions to look at the bigger picture.

> So the error with N tiles is
>
>   E[N] == X^2 E[N-1] + { error with tile size 1-X between X and 1 } ,
>
> which is more-or-less quadratic in X [somewhat confused by the mod
> in the error term], and so can be solved by "easy" calculus/algebra.
> If indeed X == 1/3 is correct for all N, then it follows immediately
> that the general solution is of form
>
>   [0, ..., 1/81, 1/27, 1/9, 1/3, 1] ,
>
> and each extra tile is taking away 8/9 of the error.  Formal proof
> and details left as an exercise ....

It seemed clear that for simple functions an optimal solution could be
obtained by algebra but it did not seem worth the effort to look, partly
because I don't know what kinds of functions Malcolm wants solutions
for.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#39784

On Friday, 17 September 2021 at 20:59:11 UTC+1, Ben Bacarisse wrote:
> Andy Walker <a...@cuboid.co.uk> writes: 
> 
> > On 17/09/2021 14:22, Ben Bacarisse wrote: 
> >> *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 
> > [...] 
> >> 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, [...] 
> > 
> > I'm still confused by the problem, by Malcolm's description 
> > of it, and by Ben's Haskell! But in the case f(x) == x, perhaps 
> > worth noting that the situation with N tiles with the last starting 
> > at X consists of the problem with N-1 tiles scaled by a factor X, 
> > together with the last tile.
> That's a good observation. I was too caught up in investigating 
> numerical solutions to look at the bigger picture.
> > So the error with N tiles is 
> > 
> > E[N] == X^2 E[N-1] + { error with tile size 1-X between X and 1 } , 
> > 
> > which is more-or-less quadratic in X [somewhat confused by the mod 
> > in the error term], and so can be solved by "easy" calculus/algebra. 
> > If indeed X == 1/3 is correct for all N, then it follows immediately 
> > that the general solution is of form 
> > 
> > [0, ..., 1/81, 1/27, 1/9, 1/3, 1] , 
> > 
> > and each extra tile is taking away 8/9 of the error. Formal proof 
> > and details left as an exercise ....
> It seemed clear that for simple functions an optimal solution could be 
> obtained by algebra but it did not seem worth the effort to look, partly 
> because I don't know what kinds of functions Malcolm wants solutions 
> for. 
> 
I've done more work on it, and I think I've found a  solution.

We start off with N given. I then create N intervals, initially evenly-spaced.

Then I start an iterative process, if a is the list of N+1 points at the previous
state, and b the list at the next stage, b is set proportionate to the square
root of the integral.

b[0] = a[0] = 0.0;
b[i] = b[i-1] + sqrt( int_f(a[i-1], a[i]))

additionally if the interval is less than one pixel, it is set to one pixel. This is a vital
step if f(x) goes to zero, otherwise you get tiny squares piling up at the low point.

Then finally we divide through by b[N] to create a list on 0.0 to 1.0.

I do this ten times, and it sems to converge on a sensible solution.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.theory

csiph-web