Stacked Hypercube Vertex Convex Hull Boundary Minimization

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Stacked Hypercube Vertex Convex Hull Boundary Minimization

Postby quintopia » Wed Jan 28, 2009 10:39 pm UTC

This is a simple-to-state problem my friend spent too long explaining to me today about which I know nothing. I thought it might be a good candidate for MMM (Massively Multiplayer Mathematics) of the smart people here. So please, throw out ideas, however small.

Let's say you have a sequence of vertices [imath]v_k, k \in [h], n \le h \le 2^n[/imath] from the n-dimensional {0,1} hypercube. From this we create an [imath]n+1[/imath]-dimensional set [imath]S = conv(<v_k,k>)[/imath], the convex hull of the sequence of vectors with their index appended. Now, we choose a constant r, such that each level set in S, [imath]L_k=\{x \in S:x_{n+1} = k\}[/imath] is contained in an n-dimensional ball, centered appropriately, of radius r.

The problem: For any h, choose the vector sequence [imath]v_k[/imath] so that r is minimized.


Questions: Is there an LP formulation of this problem? (I would guess that such a formulation would be unwieldy or unhelpful, or else this problem would not still be a problem.)
Is there a minimum h below which all solutions are trivial? (It seems to me that if h<2^i, then there is an easy upper bound on r depending on i.)
Are there any greedy-ish heuristic worth trying? Like using consecutive vertices in any hamilton cycle (i.e. a gray code ordering)? (I doubt things are this simple, but stupid ideas are worth taking a stab at first.)

itaibn
Posts: 142
Joined: Mon Dec 29, 2008 7:06 pm UTC

Re: Stacked Hypercube Vertex Convex Hull Boundary Minimization

Postby itaibn » Fri Jan 30, 2009 4:46 am UTC

Can you describe this better? Here is my best translation:

For some n, take an h such the n<=h<=2^n. Pick a sequense of points v_k in a n-dimensional {0,1} hypercube. From this we create an n+1-dimensional set S as the convex closure of all of the <v_k,k>. Now, we choose the minimal constant r, such that each L_k, defined as the set of points x in S such that *something*=k, is contained in an n-dimensional ball of radius r.

The problem: For any n and h, choose the sequence such that r is minimized.



Is there any misunderstanding? and what exactly is xn+1 supposed to mean?
I NEVER use all-caps.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Stacked Hypercube Vertex Convex Hull Boundary Minimization

Postby quintopia » Fri Jan 30, 2009 6:27 pm UTC

You repeated it the same. [imath]x_{n+1}[/imath] is simply the last component of the vector x. What would be better notation for that? Anyway, the point is that it is a level set: The set of points whose height in dimension n+1 is k.

User avatar
parallax
Posts: 157
Joined: Wed Jan 31, 2007 5:06 pm UTC
Location: The Emergency Intelligence Incinerator

Re: Stacked Hypercube Vertex Convex Hull Boundary Minimization

Postby parallax » Fri Jan 30, 2009 7:01 pm UTC

Choose h vertices from a n-dimensional hypercube. Assign each point a "Temperature" T from 1 to h, without replacement. The temperature varies linearly between the points. Minimize the size of all the isothermal surfaces.
Cake and grief counseling will be available at the conclusion of the test.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Stacked Hypercube Vertex Convex Hull Boundary Minimization

Postby Yakk » Fri Jan 30, 2009 7:06 pm UTC

quintopia wrote:This is a simple-to-state problem my friend spent too long explaining to me today about which I know nothing. I thought it might be a good candidate for MMM (Massively Multiplayer Mathematics) of the smart people here. So please, throw out ideas, however small.

Let's say you have a sequence of vertices [imath]v_k, k \in [h],[/imath]

What is [h]? The set of integers from 1 to h inclusive? 0 to h-1 inclusive? The operator that takes polynomials in h and extracts the linear term?
[imath]n \le h \le 2^n[/imath] from the n-dimensional {0,1} hypercube. From this we create an [imath]n+1[/imath]-dimensional set [imath]S = conv(<v_k,k>)[/imath], the convex hull of the sequence of vectors with their index appended.

<,> usually refers to inner products, so your use is very confusing. I think you are using it to mean <a,b>: (F^n x F) -> F^(n+1) := (a_0, ..., a_n, b)?
Now, we choose a constant r, such that each level set in S, [imath]L_k=\{x \in S:x_{n+1} = k\}[/imath] is contained in an n-dimensional ball, centered appropriately, of radius r.

So L_k is your level set in S. So r measures how 'fat' the level set is at a point is being measured by the r, I suppose, in a round about sense.

The problem: For any h, choose the vector sequence [imath]v_k[/imath] so that r is minimized.

So we want the 'fattest' part of our convex hull to be thin, in the above round sense.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Stacked Hypercube Vertex Convex Hull Boundary Minimization

Postby quintopia » Fri Jan 30, 2009 7:31 pm UTC

Yakk wrote:What is [h]? The set of integers from 1 to h inclusive?


Yes. It's a fairly common shorthand.

Yakk wrote:I think you are using it to mean <a,b>: (F^n x F) -> F^(n+1) := (a_0, ..., a_n, b)?


yes, hence "the sequence of vectors with their index appended." I just made up the notation on the spot, because everything else I thought of would have been more confusing.

User avatar
parallax
Posts: 157
Joined: Wed Jan 31, 2007 5:06 pm UTC
Location: The Emergency Intelligence Incinerator

Re: Stacked Hypercube Vertex Convex Hull Boundary Minimization

Postby parallax » Sat Jan 31, 2009 9:40 pm UTC

For example, if n=2 and h=4 you assign:
(0,0) -> 1
(1,0) -> 2
(0,1) -> 3
(1,1) -> 4

The level set for 2 goes from (0,0.5) to (1,0). so r is [imath]\sqrt 5 / 2[/imath].

This is the minimal arrangement.
Cake and grief counseling will be available at the conclusion of the test.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests