• August 14, 2022, 08:55:50 PM

Author Topic:  Article question: Julia sets you can trust  (Read 1038 times)

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Article question: Julia sets you can trust
« on: April 17, 2019, 05:43:03 AM »
claude suggested my this paper http://webdoc.sub.gwdg.de/ebook/serien/e/IMPA_A/721.pdf about partitioning the complex plane to generate Julia sets with certainty of their shape (thanks again). I am currently trying to implement their algorithm, but there is one major point I do not understand:

Where does the first black square come from?

I understand their partitioning concept of white squares (all points lie on orbits that escape, hence in the attractor basin A(inf) of infinity), black squares (all points lie on orbits that are bounded) and gray ones: unknown so far.

The rule for turning gray cells into white is clear to me: if the image of a gray square A, named f(A) only intersects with white cells (all orbits escaping), then it also must be white.

The rule for black cells states: "Color black each gray leaf cell such that no path from it reaches a white cell". That part is not clear to me.

If I knew the exact attractor basin of infinity, surely, if I could say this gray cell does not intersect with A(inf), then it must be black. But the only thing I know, are the so far computed white cells, and the union of those is contained in the true A(inf). The union surely can't be bigger (then the algorithm would have classified points falsely) but since the refinement process is discrete that computed white cells union always is strictly a subset of A(inf), otherwise one could at some point color all remaining gray cells black and would now have straight lines as boundaries between white and black - which is not the case for a fractal (or am I mistaken hiere?). So what I'm trying to say is, bluntly spoken, "there's always more white to come", so some future refinement step will eventually color a gray cell to white.

Since at the beginning of the algorithm the black region is empty, the phrase "such that no path ever reaches a white cell" means that all paths only intersect with gray cells (again, am I mistaken here?). But since more white is to come, how can I be sure that those intersected gray cells do not eventually turn into white (or some subsquare in further refinement steps)?

I would unterstand the rule "if all paths eventually lead to black cells", but since the black region is empty at the beginning, the rule would never apply.

If someone could shed light on what I am missing here, that would really help me a lot. Thanks in advance.


Linkback: https://fractalforums.org/index.php?topic=2757.0

Offline claude

  • 3f
  • ******
  • Posts: 2260
    • mathr.co.uk
Re: Article question: Julia sets you can trust
« Reply #1 on: April 17, 2019, 12:00:00 PM »
https://code.mathr.co.uk/mandelbrot-graphics/blob/823cad5aa8acc97cc530ce87202284f6dd55d8e7:/hs/lib/Mandelbrot/Graphics/Trustworthy/Julia.hs#l114 is my implementation of that step.

EDIT The general high-level idea is to detect attracting cycles within the gray part.  This is achieved by "flood fill" from the white part, recursively marking any gray cells that are reachable by backward iteration. Any gray cells that are still unreachable can be relabelled black, because their forward iteration can never touch any white cell, and so no part of the cell can escape.  The marked cells stay gray.
« Last Edit: April 17, 2019, 02:28:39 PM by claude, Reason: description of algorithmm »

Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Re: Article question: Julia sets you can trust
« Reply #2 on: April 18, 2019, 08:21:02 AM »
Thanks for the code. I'll use it when I am stuck with my implementation (I like the programming part almost more than computing images themselves, so I enjoy re-inventing the wheel, but it's a fun hobby).

Any gray cells that are still unreachable can be relabelled black, because their forward iteration can never touch any white cell

That's the part I'm confused about. Yes, if a currently available gray leaf cell does not reach any of the currently available white cells and if it reaches other gray cells - those can have white parts to come in further refinements, because, as the authors state in their article, the white cells are contained within the true A(inf), but since the true A(inf) is never actually computed (finite number of refinement, all cells have area), there is always the possibility for any gray cell to have white parts.

Or is this line of argumentation incorrect?

EDIT: What I meant to say was (and that's where I'm probably wrong in my conclusion, but I cannot see where): If I trace bacward from the white cells I currently have and find a gray cell that is not reachable from those white: since I have not computed the whole A(inf) (and never can), future white cells might be able to reach that gray cell. So marking this gray cell black would be wrong.

So, what I understand is, the gray cells are a proper superset of the Julia set boundary, the white cells are a proper subset of the true A(inf) and the black cells are a proper subset of the true interior of the Julia set.

The general high-level idea is to detect attracting cycles within the gray part.
That sounds good, but I cannot see that in their algorithm yet (more thinking required by me, I guess).


« Last Edit: April 18, 2019, 08:47:59 AM by marcm200, Reason: Clearer presentation of my line of thoughts »

Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Re: Article question: Julia sets you can trust
« Reply #3 on: April 18, 2019, 10:53:08 AM »
I just came from sprint training and got a clearer picture of my line of thought. I split it into 4 items. One of them is probably my logical mistake (sorry for repeating myself, it's the last for now, but it helps getting a line of argumentation clearer)..

1) If a gray cell does not reach the exterior of a Julia set (true A(inf)) all its orbits are bound and it can be colored black.

2) If a gray cell does not reach a somehow selected proper subset of true A(inf), nothing can be deduced whether it reaches the nonselected part of true A(inf) or not.

3) The algorithm in the paper computes white cells whose union is at any point of calculation a proper subset of true A(inf) and never the set itself.

4) Putting this together, especially 2) and 3), I'd say if a gray cell does not reach the current computed A(inf), nothing can be deduced for the still not yet computed part of true A(inf), hence it cannot be colored black.


Offline claude

  • 3f
  • ******
  • Posts: 2260
    • mathr.co.uk
Re: Article question: Julia sets you can trust
« Reply #4 on: April 19, 2019, 04:17:56 PM »
the white is true A(inf) at the current level of detail, if a cell doesn't reach it then it can never escape, so that cell can be coloured black. the iterative quad tree subdivision is simply a performance optimisation and doesn't affect the correctness (afaik).

Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Re: Article question: Julia sets you can trust
« Reply #5 on: April 19, 2019, 05:11:51 PM »
@claude: Thanks for taking the time to read through my long post. I really appreciate it!

the white is true A(inf) at the current level of detail
With true A(inf) I mean the actual complete exterior of the Julia set at infinite iterations. But the algorithm can only compute part of it - it's true in the sense, that once white - always white, but it's never all the white parts that exist. That I get. But I still think that the fact of not reaching the computed A(inf) does not allow to deduce anything about the future behavior of a gray cell for future white (probably smaller) cells.

But there are two other things I'm confused about:

They state about front propagation of black cells: "Repeatedly loop over unmarked gray cells in the cell graph. In each loop, mark all gray cells A for which f(A) intersects with computed A(inf). When a loop finishes without a single new cell being marked, the propagation stops."

Why "repeatedly"? After one loop every cell that can be marked, is, since no new cells A come to the cell graph (it's built beforehand), compued A(inf) doesn't change, neither does f(A). They probably mean some kind of recursion, but that's clearly not described.

And the second point, maybe just a typo, but: In the "reverse sweep" for black propagation, they state recursion, but over "all visited cells". That way, depending on the graph, I might mark the same cell(s) multiple times and recursively follow their edges, and if in a cycle, be stuck in an endless loop. They probably meant "all visited and yet unmarked cells".

I start to think that my line of thought is not completely wrong after all.

Maybe there is another way of getting the first black part (for Julia sets with interior) and using "if a gray cell only reaches black cells, it must also be black" as a rule for popagation.





Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Re: Article question: Julia sets you can trust
« Reply #6 on: April 20, 2019, 05:17:19 AM »
Heureka! claude's notion of the detection of cycles helped me a lot. Thanks!

I was wrong in my argumentation in, that if a gray cell reaches only gray cells, those could have white parts. They can't. If a gray cell reaches only other gray cells, those also (that I didn't see at first) only reach other gray cells, basically any of those maps its range back to the union of all the ranges, so all those gray cells have only bounded orbits and therefore black.

Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Re: Article question: Julia sets you can trust
« Reply #7 on: July 08, 2019, 10:42:01 AM »
There's another thing I do not understand so far - maybe someone can shed light on it. Thanks in advance!
(I've read that paper half a dozen or so times and hope I'm not fact-blinded and read over the explanation again and again not finding it.)

The authors state (page 6) that for the parabolic case c=-3/4 the algorithm does not find cells containing "the parabolic point" and all cells remain gray forever - in contrast to the bifurcation point at 1/4, where interior black cells can easily be found.

I started reading about parabolic Julia sets but do not understand that sentence - especially the part about "the parabolic point" within the Julia set.

Do they mean the parabolic seed value itself? But this point is always in the interior of the filled-in Julia set when it is connected since it is the first iterate of the origin's orbit. I checked by a point-sampled image, that -3/4 lies deeply in the interior and not just barely (and in the former case I think the point-sampled result can be trusted).

So my understanding of the algorithm so far was that in principle it should be possible to paint all (deep) interior black (maybe in a very high refinement), but the "gray forever" part rules that explanation out.

Or is the origin's orbit of that parabilic value so irregular that it gets arbitrarily close to the Julia set boundary? In that case with a finite square length one would always hit cells that contain points going to infinity. But that's not the case for 1/4 - so are there different levels of difficult-to-approximate parabolic Julia sets?









Offline claude

  • 3f
  • ******
  • Posts: 2260
    • mathr.co.uk
Re: Article question: Julia sets you can trust
« Reply #8 on: July 08, 2019, 01:57:18 PM »
I think the parabolic point might be one of the fixed points, like z = f(z) ? for c = 1/4 this would be 1/2 I think?  not sure.

meanwhile I found a paper in my archives stating "Mandelbrot set hyperbolicity conjecture implies Mandelbrot set computable".   "Mandelbrot locally connected" implies the hyperbolicity conjecture, and all are open problems (so are either hard to prove or false...)

EDIT Peter Hertling "Is the Mandelbrot set Computable" 2003-03-26
« Last Edit: July 08, 2019, 04:46:25 PM by claude, Reason: reference »

Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Re: Article question: Julia sets you can trust
« Reply #9 on: July 20, 2019, 07:32:33 AM »
@claude: I think you're right. In their second paper ("Rigorous bounds for polynomial Julia sets" from 2016) they talk about the fixed point of c=0.25 (page 18, last paragraph).

However in that paper they mention that their algorithm cannot find any black cells for c=0.25 as the fixed points lie on the boundary of the filled-in Julia set, hence every square that leads to that cell will inherently have a path to the outside no matter how high the refinement level. And if the basin of attraction of that fixed point is the whole interior, then no cell ever gets painted black. I can follow that argumentation.

But why is then the image for the Julia set c=0.25 in their first paper ("Images of Julia sets you can trust", page 6, bottom left) black? And for the comparison between c=0.25 (black there) and c=-0.75 (no black), which I did not understand (see my last post) - with the argumentation of the newer paper, that difference does not exist.

(I hope I did not simply read something the wrong way - if so, I'm sorry beforehand for bothering everyone).


Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Re: Article question: Julia sets you can trust
« Reply #10 on: July 31, 2019, 08:01:39 AM »
I found a difference in the parabolic quadratic Julia sets c=0.25 and c=-0.75 that might explain the sentence in the article "no such cells exist" (p6 right column).

The image below shows the two sets (upper row), point-sampled.

The middle row marks (overexaggerated) the periodic point(s): z=0.5 for c=0.25 and {z=-0.5, z=1.5} for c=-0.75, all would lie on the grid in the refinement algorithm. Important here is the observation, that in these images the fixed point for c=0.25 has interior points to its west, north and south direction, whereas no periodic point in the c=-0.75 case has any interior in the vertical direction (assuming that Julia set boundary are never pure vertical or horizontal with positive length).

In the last row, marked in red rectangles, are (overlarged) quadtree cells around the periodic points. Here one can see that all 8 cells (containing the periodic points at one corner) for c=-0.75 have a curvature in them (or exactly one definite interior point and only exterior for the rest), so they can never lie purely in the interior or the exterior and will remain gray forever, whereas in the c=0.25 case the two quadtree cells on the left of the fixed point are purely interior. If this is extrapolated from a point-sampled image that means that in principle those two cells could be judged bounded and hence colored black.

Now remains open to see, if I can find black at any computable (by me) refinement level, and why they state in their second paper that c=0.25 (with the changed algorithm using graph theory) will not find black anymore. Is one algorithm more powerful than the other?


Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Re: Article question: Julia sets you can trust
« Reply #11 on: August 01, 2019, 06:52:01 AM »
I made an experimental change to my implementation to account for those pinch.points as mentioned in my last post and could now detect black in the case c=0.25 at level 10 (see trustwrthily computed image below).

I usually construct the bounding box very conservatively: if the image of a square A, f(A) under one iteration hits a square in the plane, I expand the bounding box to that squares boundaries in every direction, which is correct but sometimes leads to too big a box. If f(A) hits a grid line at its rightmost point, then the whole square which has that grid line at its left border (that's how points are defined in my implementation) will be considered "bounding box", but only that grid line actually is. And since adjacent squares share their edges, it would suffice to include the square to the left into the bounding box. Similarly this argument could be applied to any edge (not done).

In the case of such "pinch points" in the z²+0.25 case at the fixed point, until now every path leading to that fixed point would inherently have the square right to it (exterior) in its bounding box and could never be painted black.

Now with that trimming, black emerged, but (correctly) not in the case c=-0.75 where curvature is everywhere.

I hope this line of reasoning is valid (have to think it over again). Has anyone detected any flaws in it?

(I'm not sure that I'll include this as a standard in my implementation as it's very much "built on the edge" and I prefer to have some sort of "room". I think I'd rather keep it in mind in case other pinch point-y sets are to be computed).

Offline hgjf2

  • Fractal Furball
  • ***
  • Posts: 248
Re: Article question: Julia sets you can trust
« Reply #12 on: August 04, 2019, 07:43:15 AM »
In this graphic " _parabolic_0.25.gif "; (c) from z^2+c don't seem to be 2.5 , but 2.5+0.001i due missing liniar simetry. Grey points han't right simetry.
Fractal researcher

Offline marcm200

  • 3f
  • ******
  • Posts: 1150
Re: Article question: Julia sets you can trust
« Reply #13 on: August 04, 2019, 09:22:00 AM »
In this graphic " _parabolic_0.25.gif "; (c) from z^2+c don't seem to be 2.5 , but 2.5+0.001i due missing liniar simetry. Grey points han't right simetry.
No, the value and the computation are correct.

The rotational symmetry of the gray part is a result of shrinking the bounding box to its tightest only on one end - the right border as this is the problematic one for that particular seed value. When I do it for all four sides, the result shows the right symmetry (see image below), but that takes about 40% more time to finish, so I will skip that tightening for now in the general case.


xx
I added a section to the Wikipedia article on the Mandelbrot set

Started by Duncan C on Share a fractal

2 Replies
253 Views
Last post January 20, 2020, 06:12:52 PM
by Duncan C
clip
when you're new to Mandelbulb3D and you are rendering your first animation

Started by Nasko on Fractal Humor

10 Replies
3865 Views
Last post April 29, 2020, 01:01:17 AM
by Tas_mania
clip
Can you help me identify this (possibly) fractal?

Started by username on Share a fractal

5 Replies
1073 Views
Last post January 03, 2019, 12:02:36 PM
by mrrudewords
clip
can you identify this fractal ?

Started by Adam Majewski on Noob's Corner

49 Replies
769 Views
Last post July 02, 2022, 08:53:13 PM
by Adam Majewski
xx
Can you run a Kalles Fraktaler job on a Linux Server?

Started by Kartoffel on Noob's Corner

4 Replies
86 Views
Last post April 21, 2022, 07:49:05 PM
by Kartoffel