Article question: Julia sets you can trust

  • 6 Replies
  • 130 Views

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • *
  • Fractal Feline
  • **
  • Posts: 179
« on: April 17, 2019, 07: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.

Offline claude

  • *
  • 3e
  • *****
  • Posts: 1004
    • mathr.co.uk
« Reply #1 on: April 17, 2019, 02: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, 04:28:39 PM by claude, Reason: description of algorithmm »

Offline marcm200

  • *
  • Fractal Feline
  • **
  • Posts: 179
« Reply #2 on: April 18, 2019, 10: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, 10:47:59 AM by marcm200, Reason: Clearer presentation of my line of thoughts »

Offline marcm200

  • *
  • Fractal Feline
  • **
  • Posts: 179
« Reply #3 on: April 18, 2019, 12:53:08 PM »
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

  • *
  • 3e
  • *****
  • Posts: 1004
    • mathr.co.uk
« Reply #4 on: Yesterday at 06: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

  • *
  • Fractal Feline
  • **
  • Posts: 179
« Reply #5 on: Yesterday at 07: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

  • *
  • Fractal Feline
  • **
  • Posts: 179
« Reply #6 on: Today at 07: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.


xx
Embedded Julia sets

Started by pauldelbrot on Image Threads

57 Replies
2823 Views
Last post April 06, 2019, 06:49:01 AM
by pauldelbrot
clip
Quadratic Julia sets

Started by pauldelbrot on Image Threads

11 Replies
445 Views
Last post June 18, 2018, 06:15:08 PM
by pauldelbrot
clip
Sectionally defined Julia sets

Started by marcm200 on Image Threads

3 Replies
128 Views
Last post April 03, 2019, 04:32:29 PM
by marcm200
clip
Julia and Mandelbrot sets using Lyapunov sequences

Started by marcm200 on Image Threads

22 Replies
463 Views
Last post April 12, 2019, 08:46:30 AM
by marcm200
xx
Julia sets: True shape and escape time

Started by marcm200 on Fractal Mathematics And New Theories

3 Replies
133 Views
Last post March 31, 2019, 09:33:24 AM
by marcm200