<p>Given an algebraic variaties of  n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?</p>

<p>And if there is, what is the computational complexity of the algorithm?</p>

CC BY-SA 3.0
2017-11-04T12:56:25.703Z
The [WIkipedia article on the inscribed square problem](https://en.wikipedia.org/wiki/Inscribed_square_problem) says "H.W. Guggenheimer proved that every hypersurface $C^3$-diffeomorphic to the sphere $S^{n−1}$ contains $2^n$ vertices of a regular Euclidean n-cube." Perhaps this proof leads to an algorithm in this case.
Joseph O'Rourke
CC BY-SA 3.0
2017-11-04T13:07:48.487Z
@JosephO'Rourke thank you, I have just read the wiki, it says that the general case is open. I think there is an algorithm, but I am not sure what tit's computational complexity is.
XL _At_Here_There
CC BY-SA 3.0
2017-11-04T13:32:52.557Z
I have just found that Terrency Tao has an article and blog on the problem, terrytao.wordpress.com/2016/11/22/… But it is so long, I can not read through it ,possibly, He thinks about the problem in too complicate way.
XL _At_Here_There
CC BY-SA 3.0
2017-11-05T04:14:47.277Z
https://terrytao.wordpress.com/2016/11/22/an-integration-approach-to-the-toeplitz-square-peg-problem/
XL _At_Here_There
CC BY-SA 3.0
2017-11-09T18:57:56.540Z
You might also look at Emich's result (see the above Wikipedia article), which works in the curve case for piecewise analytic curves. Varieties are always piecewise analytic (at least, at smooth points), so if you could generalize Emich...
Joshua Grochow
CC BY-SA 3.0
2017-11-10T08:38:47.673Z
@JoshuaGrochow I think there is an algorithm and the algorithm is about in the NPC class of the computational complexity, thank you for your comment.
XL _At_Here_There
<complexity-classes><computational-geometry>
Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?
XL _At_Here_There
# Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?

(Asked by: username_0 on 2017-11-04)

Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?

And if there is, what is the computational complexity of the algorithm?

**Tags:** complexity-classes, computational-geometry
> **Comments:**
> **username_1**: The [WIkipedia article on the inscribed square problem](https://en.wikipedia.org/wiki/Inscribed_square_problem) says "H.W. Guggenheimer proved that every hypersurface $C^3$-diffeomorphic to the sphere $S^{n−1}$ contains $2^n$ vertices of a regular Euclidean n-cube." Perhaps this proof leads to an algorithm in this case.  
> **username_0**: @JosephO'Rourke thank you, I have just read the wiki, it says that the general case is open. I think there is an algorithm, but I am not sure what tit's computational complexity is.  
> **username_0**: I have just found that Terrency Tao has an article and blog on the problem, terrytao.wordpress.com/2016/11/22/… But it is so long, I can not read through it ,possibly, He thinks about the problem in too complicate way.  
> **username_0**: https://terrytao.wordpress.com/2016/11/22/an-integration-approach-to-the-toeplitz-square-peg-problem/  
> **username_2**: You might also look at Emich's result (see the above Wikipedia article), which works in the curve case for piecewise analytic curves. Varieties are always piecewise analytic (at least, at smooth points), so if you could generalize Emich...  
> **username_0**: @JoshuaGrochow I think there is an algorithm and the algorithm is about in the NPC class of the computational complexity, thank you for your comment.  

---

## 0 answers

