Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Wow yeah agreed. Direct link for convenience:

https://www.ics.uci.edu/~eppstein/junkyard/euler/noah.html



The proof is elegant, but the whole flooding process on arbitrary polyhedron may be a bit difficult to follow (especially if you are trapped by details like saddles above some peaks, lakes with different altimeters, and how gravity works over the polyhedron).

The following simpler formulation of the flooding process may be easier to follow.

  initial state: num_islands=1; num_lakes=V
  final state:   num_islands=F; num_lakes=1
  how state changes: Each time a saddle sinks, either two lakes are joined (num_lakes--) or an island is split (num_islands++)
The whole process takes (F-1)+(V-1) events to finish, which is equal to the number of saddles E.


Thank you, you have helped to make it more clear for me!


If anyone else struggles with how the formulae "V-J=1" and "1+D-F=0" are obtained: You can think of the two different ways of joining bodies of water (join two separate bodies of water (J) and join the same body of water (D)) as algorithms for computing a spanning tree in the original graph (J) and the dual graph (D).


To emphasize where the topology comes in since it wasn't clear to me at first: the important bit is the saddles. Just before a saddle goes under, there are two important properties

1. there are land masses on both sides of the saddle. This would not be true if the polytope had holes.

2. if the lakes on either side of the saddle are joined up, the only way they can do that is if the lake circles around and encloses at least one of the two land masses (Jordan curve theorem). Once the saddle point goes under, that land mass is cut off from the "mainland". This would not be true if the polytope had a handle. The lakes could be joined up by going along the handle without enclosing one of the land masses.

https://i.imgur.com/I2FqwWQ.jpg




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: