Smallest circumscribing n-sphere for non-orbiform polytope

Discussion of tapertopes, uniform polytopes, and other shapes with flat hypercells.

Smallest circumscribing n-sphere for non-orbiform polytope

Postby quickfur » Thu Mar 15, 2018 4:46 pm

Given an n-polytope, not necessarily orbiform, how would one find the smallest n-sphere that circumscribes the polytope?

Or equivalently, how to define a "center" for some arbitrary polytope P such that if P is orbiform, then the circumscribing sphere will be centered on this "center"?
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Smallest circumscribing n-sphere for non-orbiform polyto

Postby Klitzing » Thu Mar 15, 2018 6:00 pm

There are at least 2 distinct standard methods available in order to define a "center":
  • either use the medium of the vertices, i.e. when vi = vector to the i-th vertex, then c = sum( {vi | 1 <= i <= n} )/n
  • or you consider the continuous volume of the full body as body-center, i.e. you define the set X of all points x within the body of the polytope, take some point y in X and consider for that Y = integral |x-y| dx, which thus defines a mapping f(y) = Y; then consider c = f-1( min {Y | y in X} ).
    Nota bene, the mapping f is not generally invertable. But at least for non-degenerate polytopes that point c should be unique none-the-less. In fact, you would have df/dx (c) = 0.

Wrt. the smallest circumsphere you could test either one when applied to a 3D regular based upright n-pyramid of arbitrary height:
But then you'd see that when n goes up and the height becomes rather low, then the circumcenter clearly lies somewhere beyond the base. Whereas both above defined centers always would clearly lie inside the shape. Therefore those won't serve useful here ... :(

--- rk
Klitzing
Pentonian
 
Posts: 1637
Joined: Sun Aug 19, 2012 11:16 am
Location: Heidenheim, Germany

Re: Smallest circumscribing n-sphere for non-orbiform polyto

Postby quickfur » Thu Mar 15, 2018 7:01 pm

Hmm you're right. A shallow pyramid would induce a large circumsphere, so it would not be useful in defining a "center". :(

I guess the ultimate goal of this is automatic placement/scaling in my polytope viewer program, so that given some arbitrary polytope P, it would find a length-preserving transformation that would center the object within view and also scale it to fit the viewport. Centering on the medium of vertices + scaling to max distance of vertex from the medium serves as a sufficient approximation to this, I suppose. But I can think of many cases where this would be suboptimal (e.g., a spindle-shaped object would need different scaling depending on the viewpoint, and in a square viewpoint a rotated object might fit better, e.g., rotated diagonally). Such is life, I guess. :lol:
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Smallest circumscribing n-sphere for non-orbiform polyto

Postby quickfur » Thu Mar 15, 2018 7:05 pm

Maybe then we should consider these as two different questions:

1) What's the simplest/best way to translate/scale some object such that it fits within some given viewpoint?

2) How to check whether some polytope P is orbiform, and how to compute the circumsphere?

A somewhat related (but not so important) question is whether there's a meaningful definition for a maximal in-sphere for a polytope P that is not necessarily convex. I can think of several non-convex cases where it would imply multiple in-spheres, and may require global optimization to find the maximal one (and also it would not be of much use :lol:). But if we restrict P to be convex, can there be a meaningful definition of a maximal in-sphere? Is it possible to make it unique?
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Smallest circumscribing n-sphere for non-orbiform polyto

Postby Klitzing » Fri Mar 16, 2018 12:27 pm

what about simply centering between the maximal and minimal coordinate extends each?
--- rk
Klitzing
Pentonian
 
Posts: 1637
Joined: Sun Aug 19, 2012 11:16 am
Location: Heidenheim, Germany

Re: Smallest circumscribing n-sphere for non-orbiform polyto

Postby quickfur » Fri Mar 16, 2018 3:13 pm

Ohh, that's an interesting idea. That would optimize it for a hypercubic viewport, I suppose. I'll try it out and see!
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Smallest circumscribing n-sphere for non-orbiform polyto

Postby quickfur » Fri Mar 16, 2018 3:17 pm

Also, what about the orbiform question? Is it just a matter of taking the first (n+1) vertices and computing the equation of the n-sphere, and then checking that the rest of the vertices lie on it?
quickfur
Pentonian
 
Posts: 2935
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North


Return to Other Polytopes

Who is online

Users browsing this forum: No registered users and 13 guests

cron