Fibonacci Sphere
extremelearning.com.au
extremelearning.com.au
In fact, the general strategy works for higher dimensions as well. Spread some points on the hypersurface of a unit 3-sphere with some kind of energy minimalization simulation, and the resulting array of 4D unit vectors can can be used to compress quaternions!
import math
def fibonacci_sphere_point(idx, num_points):
i = idx + 0.5
phi = math.acos(1 - 2 * i / num_points)
golden_ratio = (1 + 5 ** 0.5) / 2
theta = 2 * math.pi * i / golden_ratio
sin_phi = math.sin(phi)
cos_phi = math.cos(phi)
sin_theta = math.sin(theta)
cos_theta = math.cos(theta)
return (
cos_theta * sin_phi,
sin_theta * sin_phi,
cos_phi,
)
table = [fibonacci_sphere_point(i, 1024) for i in range(1024)]
def sqr_dist(a, b):
return (a[0]-b[0])**2 + (a[1]-b[1])**2 + (a[2]-b[2])**2
def decode(value):
return table[value]
def encode(point):
closest_idx = 0
closest_dist2 = sqr_dist(point, table[closest_idx])
for i in range(1, len(table)):
curr_dist2 = sqr_dist(point, table[i])
if closest_dist2 > curr_dist2:
closest_dist2 = curr_dist2
closest_idx = i
return closest_idx def fibonacci_sphere_point(idx, num_points):
i = idx + 0.5
phi = math.acos(1 - 2 * i / num_points)
golden_ratio = (1 + 5 ** 0.5) / 2
theta = 2 * math.pi * i / golden_ratio
sin_phi = math.sin(phi)
cos_phi = math.cos(phi)
sin_theta = math.sin(theta)
cos_theta = math.cos(theta)
return (
cos_theta * sin_phi,
sin_theta * sin_phi,
cos_phi,
)
As I describe in the article, different methods produce similar but slightly different solutions. An optimal solution for one objective function, may not be the optimal for a different objective function. I then give details about how the solution that optimizes volume of the convex hull is different to the solution that optimizes for packing distance, etc.
If you just want N in a certain range, we can use the triangle-based polyhedron and successively quadruple or triple the number of faces. Then use the face normals as points. This gives visually appealing distributions without any real oddities.
Things get interesting when you also allow the sphere to grow, the spots start to split (and sometimes annihilate), understanding how the spots move on the sphere is itself a very interesting problem.
I've had Nash's infinitely collapsible sphere stuck in my head for some time: https://www.quantamagazine.org/mathematicians-identify-thres...
For purposes of nearest neighbors this seems like an incredibly interesting shape to inscribe into: The sphere, despite having spherical properties also maintains linear properties due to the corrugation. To me that means we can try to inscribe orthogonal properties into both of the spaces.
My understanding of these geometries isn't complex enough to make the connections, so my question is this: Do you think its feasible to use shapes with this 'corrugated' property to make better nearest neighbor compression? My intuition tells me that you can use the shape's linear nature to push apart independent components and inscribe the rest of the details into the spherical components. Or perhaps the opposite way.
Hopefully that made sense!
Good article, but it'll take some time to understand it. %1 is interesting, I used to use {..} for taking fractional part, %1 is intuitively easy, though not looking particularly good...
Regarding the two-variable function mod(x,b). Typically this is written as x (mod b) in maths, and as x%b in computing.
It is generally well known that for positive integers x and b, the output of this function is the remainder when x is divided by b.
However, what is less well-known is that if b=1, then the convention is that:
x (mod 1) = x%1 = fractional part of x.
For example, Python, Excel both implement this special convention.
As far as i understand, part of the story as to why dodecahedron and the cube fall short is due their non-triangular faces.
Icosahedron: 12 points, 20 faces (and 30 edges)
Dodecahedron: 20 points, 12 faces (and 30 edges)
"The first is that this mapping is area-preserving, not distance-preserving." Which area is being preserved?
Is there a volume preserving choice function?
What are points t0 and t3, are those the location of the singularity points? What is the definition of those "singularity points"? Is it that seeming void in the center of the fibonacci spiral? And that void doesn't exist within the unit square case?
I especially enjoyed footnote #1.
So[0,1)^1 is a line interval, [0,1)^2 is a unit square and [0,1)^3 is the unit cube, and [0,1]^d is a d-dimensional cube.
2.Only one boundary can be included
It includes 0 but not 1 because it can only the context is usually that practitioners want a region where one edge will wrap to the opposite edge. Thus they treat [0,1)^2 as if it is actually a 2-dimensional torus.
thus the the 2 boundaries acutally map to the same point, so you can only include one of them. In our case as we are using x %1 = fractional part of x, the fractional part could be 0, if x=3.0, but it could never be exactly 1.
3) the mapping from the circle to the surface of the sphere is described here https://en.wikipedia.org/wiki/Lambert_azimuthal_equal-area_p...
the entire top edge of the square maps to the north pole, and the entire bottom edge maps to the south pole.
4.) t0 is the first point, t3 is the 4-th point.
Hope that helps!