Tricky Mandelbrot Problem

Perkdawg

Forums Newbie

Posts: 2

« on: April 11, 2017, 03:57:29 AM »

Hi everyone,
Here is the basic rule of the question:
Take two random points in a structure and measure the distance between them. (straight lines only) What is the average value of the distance?

This problem is actually relatively well studied when it comes to finite structures. For example, a circle with a radius 1 has an average distance of 128/45π. For finite structures, the value can be estimated quite easily through clever programming. The tricky part is finding the exact value.

Where I'm getting stuck is when I try to apply this problem to fractals. Fractals—being inherently infinite—make finding the exact value very difficult. (If not impossible) Another problem is that computing random numbers is inherently non-random, (hence the pseudorandom) so even the estimates will be a little off. I coded a little tester and got an approximate answer of ~.69. (Bailout value was 2) Anyone have any suggestions on how to solve the problem or at least get a more accurate estimate?


« Last Edit: April 11, 2017, 09:53:41 PM by Perkdawg, Reason: Clarification »	Logged

claude

Fractal Bachius

Posts: 563

Re: Tricky Mandelbrot Problem

« Reply #1 on: April 11, 2017, 05:13:43 AM »

I tried a couple of 1D examples:

Unit length line segment: d = 1/3

see https://math.stackexchange.com/questions/195245/average-distance-between-random-points-on-a-line though I calculated it in a different way (double integration with left and right parts)

Cantor middle-third fractal: d = 1/2

I found the fractal's distance like this:

Call the unknown distance d.
Then there's a P=1/2 chance that both points are in the same half of the fractal, in which case the average distance is d/3 by simple scaling.
There's also a P=1/2 chance that both points are in opposite halves, in which case the average distance is d/3 + 2/3 (distance within the half, plus distance between halves)
So d = (1/2)(d/3) + (1/2)(d/3 + 2/3) which gives d = d/3 + 1/3 so 3 d = d + 1 so 2 d = 1 and d = 1/2

As a sanity check, the fractal has "holes" so some "near" points are missing, which means the expected distance should be greater than for a "whole" line segment, as there are still "far" points.

For the Mandelbrot set however, I doubt you can get better than a statistical/Monte-Carlo method - as its implicitly defined via iteration.

See also attempts to calculate the area of the Mandelbrot set. As far as I'm aware it's not known if the boundary of the set has positive area, assuming it doesn't then you could possibly compute something based on the interior of hyperbolic components (I can't remember if it's been proven or otherwise that these are the only components in the quadratic Mandelbrot set).


	Logged

Tglad

Fractal Molossus

Posts: 703

Re: Tricky Mandelbrot Problem

« Reply #2 on: April 11, 2017, 05:55:44 AM »

For a lot of fractal shapes the average distance will be infinite, e.g. a Koch curve, Minkowski sausage.
I suspect it is the same for the mandelbrot set, the filaments follow a rough curve and get extremely thin, so I would guess that they will tend the average length up to infinity.

Claude, the Cantor middle-third fractal (1D Cantor dust) is nowhere dense is it not? In which case you can never travel from one point in the set to any other.

I think the average distance would be finite for the Menger carpet / Sierpinski triangle, but could be greater than the length of a side. The Manger carpet probably has average length of a little over 2/3 of its width. 1/3 to travel vertically, 1/3 horizontally and a bit more because occasionally you have to navigate around a hole.

I wonder what it is for Brownian noise... I suspect it would also be infinite.


	Logged

claude

Fractal Bachius

Posts: 563

Re: Tricky Mandelbrot Problem

« Reply #3 on: April 11, 2017, 06:14:35 AM »

Quote from: Tglad on April 11, 2017, 05:55:44 AM

For a lot of fractal shapes the average distance will be infinite

True if you take distance to be along the shortest wiggly path within the shape. But I assumed it was straight line distance not necessarily within the structure, and I get values from my numerical code that roughly match the 0.69 quoted above (0.6754 is my current estimate, will post more in about an hour by which time I'll have another datum..)


	Logged

Tglad

Fractal Molossus

Posts: 703

Re: Tricky Mandelbrot Problem

« Reply #4 on: April 11, 2017, 06:36:11 AM »

Oh, I see. That sounds a lot more possible to get analytic results... though still tricky I imagine.


	Logged

claude

Fractal Bachius

Posts: 563

Re: Tricky Mandelbrot Problem

« Reply #5 on: April 11, 2017, 07:44:47 AM »

some numbers

Code:

# size  distance
8       0.674814978431537815
9       0.675380757066682991
10      0.675481626317913308
11      0.675421703068835644

generated by stupid brute force code (the mandelbrot generation is super fast, the distance code takes 100s of times longer):

Code:

#include <stdio.h>
#include <mandelbrot-graphics.h>

int main(int argc, char **argv) {
  complex double c = -0.75 + I * 0.0;
  double r = 1.5;
  m_pixel_t black = m_pixel_rgba(0, 0, 0, 1);
  m_pixel_t white = m_pixel_rgba(1, 1, 1, 1);
  double er = 600;
  int maxiters = 1000000;
  for (int b = 8; b < 16; ++b)
  {
    int w = 1 << b;
    int h = 1 << b;
    m_image *image = m_image_new(w, h);
    if (image) {
      m_d_transform *transform = m_d_transform_rectangular(w, h, c, r);
      if (transform) {
        complex double c0 = 0;
        complex double dc0 = 1;
        m_d_transform_forward(transform, &c0, &dc0);
        double px = cabs(dc0);
        m_d_colour_t *colour = m_d_colour_minimal(black, white, white);
        if (colour) {
          m_d_render_scanline(image, transform, er, maxiters, colour);
          char filename[100];
          snprintf(filename, 100, "%d.png", b);
          m_image_save_png(image, filename);
          double s = 0;
          double n = 0;
          #pragma omp parallel for reduction(+:s) reduction(+:n) schedule(static, 1)
          for (int y1 = 0; y1 < h; ++y1)
          {
            double s0 = 0;
            double s1 = 0;
            for (int x1 = 0; x1 < w; ++x1)
              if (white != m_image_peek(image, x1, y1))
                for (int y2 = 0; y2 < h; ++y2)
                  for (int x2 = 0; x2 < w; ++x2)
                    if (white != m_image_peek(image, x2, y2))
                    {
                      s0 += 1.0;
                      s1 += hypot(x1 - x2, y1 - y2);
                    }
            s1 *= px;
            n = n + s0;
            s = s + s1;
          }
          s /= n;
          printf("%d	%.18f
", b, s);
          fflush(stdout);
          m_d_colour_delete(colour);
        }
        m_d_transform_delete(transform);
      }
      m_image_delete(image);
    }
  }
  return 0;
}

attached is the final image, the center of every non-white pixel is interior to the Mandelbrot set.

EDIT to add: this paper is interesting on the general "rule" mentioned in the original post: https://wwwmath.uni-muenster.de/reine/u/burgstal/d18.pdf

another EDIT: some numbers taking into account the boundary as well as the interior - the filaments are very thin so these greatly overestimate the thickness. see also second image

Code:

8       0.767666868213363052
9       0.747378308995076845
10      0.732747389502671487
11      0.720950714462732734

11.png (110.04 KB, 2048x2048 - viewed 75 times.) 11e.png (131.58 KB, 2048x2048 - viewed 76 times.)
« Last Edit: April 11, 2017, 10:42:26 AM by claude, Reason: more numbers »	Logged

Perkdawg

Forums Newbie

Posts: 2

Re: Tricky Mandelbrot Problem

« Reply #6 on: April 11, 2017, 09:45:03 PM »

Good work claude and thanks for the help Tglad.
So at this point, we can conclude the answer is probably somewhere between .67 and .69, which is actually strangely close to e/4. (this, however is most likely a coincidence) Considering that not even the area of the mandelbrot has been calculated to an exact value, I can guess that the same is true with this question. It's unfortunate yet also intriguing because the actual value could be an even ratio or some odd conglomerate of known mathematical constants, yet it would be exceptionally difficult—if not impossible—to find using known mathematical concepts. I'll keep fiddling, and I will post in this thread if I discover anything of interest. Thanks again for the help!


	Logged

lkmitch

Fractal Lover

Posts: 238

Re: Tricky Mandelbrot Problem

« Reply #7 on: April 12, 2017, 06:52:30 PM »

The numerical estimate of the mean distance will depend on the number of iterations and the number of points used. When I estimated the area of the Mandelbrot set (1.506484), I used a limit approach. I estimated the area using combinations of iteration count and number of points and estimated the limit as both went to infinity. Perhaps a similar approach would work here.


	Logged

Pages: [1] Go Down

« previous next »

	Author	Topic: Tricky Mandelbrot Problem (Read 735 times)
		Description: Average distance between two random points on the Mandelbrot Set.
0 Members and 1 Guest are viewing this topic.

Related Topics
	Subject	Started by	Replies	Views	Last post
	Install Problem Mandelbulber	JJS	3	1916	November 05, 2011, 04:34:25 AM by JJS
	Problem with Mandelbrot Distance Estimator Mandelbrot & Julia Set	Levi	14	2564	February 20, 2015, 04:13:13 PM by Adam Majewski
	Mandelbrot Set Distance Estimator Rendering Problem UltraFractal	aleph0	5	1208	April 30, 2014, 01:08:45 AM by aleph0
	Mandelbrot distance estimation problem Help & Support	Iariak	7	248	November 19, 2016, 04:14:35 PM by Iariak
	Problem with Normalized Iteration Count at High Zoom (Mandelbrot, Python) Help & Support	mandelbro82	1	150	April 02, 2017, 07:57:00 PM by mandelbro82

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!

	Welcome, Guest. Please login or register.	October 01, 2018, 02:45:15 PM
		Login with username, password and session length

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval, thanks and see you perhaps in 10 years again

The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again