Finding Convex Hulls in hyperbolic spaces

[Hyperbolful]

I am trying to find the convex hull of a finite set in a hyperbolic space, particularly the Poincare disk, but the Upper Half plane works as well.

I know the following equivalent definitions of the Convex Hull:
1) It is the smallest convex set containing the points
2) If the set is discrete, then every point in the sets convex hull is a convex combination of the points in the set.
3)It is the intersection of all the half-spaces containing the set.

because of the metric on the poincare disk I am trying to use (3) as my main tool to find the convex hull, and I have started reading on polyotopes.

My question is what is the convex hull of points that lie on the same geodesic in the poincare disk? My guess is just the geodesic they are on, but I'm not sure that this agrees with (3)

Any pointers?

 

[chiro]

You can use the definition of the angle to find your convex hull.

My suggestion is to use the inner product based on the norm that your geometry uses (ie use the definition of the norm and its relationship to the inner product to define the inner product).

Convex hull algorithm as a general algorithm is essentially a maximization problem.

You are basically maximizing the "inner product" you make with every half-space. Its easier to explain the 2D case with this "maximization" criterion.

So in 2D you find the point with the lowest y coordinate. If there are multiple points with the same y-coordinate choose the one with the highest x-coordinate (positive).

The first vector you use is basically a unit vector on the positive x-axis. You then use the inner product to compare two vectors: one on the current "direction" vector and another based on the direction vector (unit size) that goes from the current "testing" point to every other point.

The point that yields the highest inner product, becomes the next point in the ordered list of the hull.

In higher dimensions, you replace "line" with a higher dimensional polytype like a "plane" or a hyperplane.

 

[Hyperbolful]

Firstly thanks for your response.

I actually haven't ever heard of it as an optimization of an innerproduct before.
Im not sure what I could use for my "x-axis" though. I'm working in 2D in the poincare disk with the usual metric in place. Could I just use the typical complex plane coordinates but under the poincare metric?

 

[chiro]

The maximization of an inner product with unit vectors is the same as the minimization of an angle.

When you're trying to find the next "line" or "plane" in your hull chain you're essentially finding the linear object. If the inner product was -1 then your point is collinear but on the wrong side. If it is +1 then it is collinear on the right side.

Essentially you are going to go counter-clockwise where the angle is minimized.

Its probably a good exercise to get a blank piece of paper and put down 10-20 points arbitrarily and put one point at a y value lower than the rest. From that y-value draw a line y = yvalue. Now draw the hull and take notice of the relationship of every line and its relationship to the previous line and the "minimization of angle" (or maximization of inner product) should jump out at you.

If you can use your metric to generate an inner product and the inner product is a valid one, I think it should be ok. I'm not an expert on non-euclidean geometry, but I'm 90% certain that if you have a valid inner product that is generated from the metric, then it should work.

If someone knows more about inner products on non-euclidean geometries please jump in.

 

[Hyperbolful]

Chiro

Thanks for the little exercise, I see how it works in euclidean space, but I'm worried now that it won't generalize to the poincare disk. My metric is pretty obscure and involves logarithms of ratios of euclidean norms, and it seems like a stretch that an innerproduct induced from it will have the same relation to angles as the dot product in R^n.

I might be missing something, but I'm still going to try it since one of the advantages of the poincare disk is that its conformally equivilent to the upperhalf plane, so the angles might very well work out to be related by different inner products