User han - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:49:08Z http://mathoverflow.net/feeds/user/17332 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80242/complexity-of-detecting-a-convex-body-in-mathbbrn Complexity of detecting a convex body in $\mathbb{R}^n$? han 2011-11-06T20:57:30Z 2011-11-07T19:14:12Z <p>Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that,</p> <ol> <li>$K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.</li> <li>The boundary between $K_1$ and $K_2$ is unknown. (To avoid the trivial case, I assume that the boundary is not a hyperplane.)</li> <li>Either $K_1$ or $K_2$ is a convex set, but we don't know which one is.</li> <li>We have two initial points $\mathbf{x},\mathbf{y}$ on hand, where $\mathbf{x}\in K_1$ and $\mathbf{y}\in K_2$.</li> </ol> <p>Essentially, $K_0$ can be viewed as a black box. Further assume that one can query any point in $K_0$ with a <em>membership oracle</em>, namely a procedure that given a point $\mathbf{p}\in K_0$, reports the set contains $\mathbf{p}$. </p> <p><strong>The goal is to determine which set is convex using membership queries.</strong></p> <p>My questions:</p> <ol> <li>Can this be done with <em>finite</em> number of queries?</li> <li>What is the complexity class of this problem?</li> </ol> <p>Thanks.</p> http://mathoverflow.net/questions/76345/upper-and-lower-bounds-of-the-total-surface-area-of-convex-polytopes-that-partiti Upper and Lower Bounds of the Total Surface Area of Convex Polytopes that Partition a Hypercube han 2011-09-25T16:41:22Z 2011-09-25T16:41:22Z <p>Let $C$ be a hypercube in $\mathbb{R}^D$ with edge length of $L$. Let $\mathcal{P}_1,\ldots,\mathcal{P}_K$ be $K$ convex polytopes that partition $C$. Let $S_k$ be the surface area of the polytope $\mathcal{P}_k$, where $k\in \{1,\ldots, K \}$. Define $S=\sum_{k=1}^K S_k$, what is the upper bound and lower bound of $S$? In particular, I'm interested in the bounds which can be expressed as function of $K,D$ and $L$.</p> <hr> <ol> <li><p>In case it is not clear, the <em>surface area</em> of a convex polytope $\mathcal{P}$ is the sum of $(D-1)$-dimensional Lebesgue measure of the facets of $\mathcal{P}$.</p></li> <li><p>There may have some nice results when $K\rightarrow\infty$ and reformulating this problem as a tessellation induced by some random processes. However, I'm interested in small $K$, say $1&lt; K&lt;50$. </p></li> <li><p>I guess this problem has been solved, but I'm struggling to find good literature.</p></li> </ol> http://mathoverflow.net/questions/75413/angle-btween-coordinate-vector-and-normal-vector-of-facet-in-a-convex-polytope-a Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample han 2011-09-14T15:28:28Z 2011-09-15T04:01:02Z <h2>Definitions</h2> <p>Let $\mathcal{C}$ be a convex polytope in $\mathbb{R}^{D}$ with $K$-facets $F_{1},\ldots,F_{K}$. I denote the normal vector of the $k^\mathrm{th}$ facet as $\mathbf{w}_k=(w_{k1},\ldots,w_{kD})$. </p> <p>In the sequel, I will use $k$ as the index of $K$ facets and $d$ as the index of $D$ dimensions. Namely, $d\in \{1,\ldots,D\}$ and $k\in \{1,\ldots,K\}$.</p> <p>Let $\mathbf{p}=(p_{1},\ldots,p_{D})$ be a point in $\mathbb{R}^{D}$. Define</p> <p>$L_{d}=\{\mathbf{p}+\theta\mathbf{u}_{d}|\theta\in \mathbb{R}\},$</p> <p>where $\mathbf{u}_{d}$ is the vector of the form $(0,\ldots,0,1,0,\ldots,0)$ with a $1$ only at the $d^{\mathrm{th}}$ dimension.</p> <p>For $k=1,\ldots, K$, define</p> <p>$G_{k}=\{d|L_{d}\cap F_{k}\neq \emptyset\}.$</p> <p>Define $f:\mathbb{R}^{D}\times\mathbb{R}^{D}\rightarrow [0,1]$ as</p> <p>$f(\mathbf{x},\mathbf{y})=\frac{|\mathbf{x}^\mathrm{T}\mathbf{y}|}{\left\|\mathbf{x}\right\|\left\|\mathbf{y}\right\|}.$</p> <h2>My conjecture</h2> <p>For any $\mathbf{p}\in \mathrm{int}\mathcal{C}$, there exist $d$ and $k$ such that $d\in G_{k}$ and $f(\mathbf{u}_{d},\mathbf{w}_{k})=\max \{f(\mathbf{u}_{1},\mathbf{w}_{k}),\ldots,f(\mathbf{u}_{D},\mathbf{w}_{k})\}$.</p> <p>Can anyone provide a counterexample?</p> <h3>An illustrative example in $\mathbb{R}^2$</h3> <p>In particular, if we restrict ourself in $\mathbb{R}^2$, the above conjecture can be restated as follows:</p> <p>Let $p$ be a point in the interior of a convex polygon $\mathcal{C}$. Let $L_x$ and $L_y$ be two lines through $p$, which are parallel to $x$-axis and $y$-axis respectively. Consider all acute angles at intersections of $L_x$ $L_y$ and $\partial \mathcal{C}$, there is at least one angle $\geq$45°.</p> <p>The figure below gives an example.</p> <p><img src="http://home.in.tum.de/~xiaoh/q1p1.png" alt="alt text"></p> <p>I haven't found any counterexample in $\mathbb{R}^2$, and that's why I'm considering to generalise this conjecture into high dimensional space.</p> <p>Finally, any problem reformulation is also welcome.</p> http://mathoverflow.net/questions/73511/draw-a-random-line-through-a-voronoi-tessellation-what-is-the-average-number-of Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects? han 2011-08-23T17:17:45Z 2011-08-27T10:19:33Z <h2><strong>Update: problem reformulation</strong></h2> <p>Following the advice in comments, I now restate my problem using Voronoi tessellation.</p> <p>Given a unit hypercube $H_n=\{(x_1,\ldots,x_n)\in \mathbb{R}^n: 0\leq x_i\leq 1\}$, generate $K$ random points in $H_n$ using uniform Poisson point process with intensity 1. </p> <p>Let $V_k$ be the $k$-th Voronoi cell. Define</p> <p>$\mathcal{V}=\{k\in\{1,\ldots,K\}|L\cap V_{k}\neq \emptyset\}$,</p> <p>where $L$ is a line that intersects $H_n$</p> <h3>My question</h3> <p>Assume that $L$ is a random line (i.e. $L$ is uniformly distributed over all lines that intersect $[0,1]^n$), what is the expected value of $|\mathcal{V}|$? i.e. what is the average number of Voronoi cell that a random line intersects?</p> <h3>Clarification of edits</h3> <ol> <li><p>In the last formulation, $K$ points were uniformly distributed on $[0,1]^n$. <em>Anthony Quas</em> suggests that using a Poisson point process is preferable. </p></li> <li><p>My original definition of a random $L$ is: the end points of $L$ are uniformly distributed on $H_n$'s edges. However, in <em>Remark</em>'s comment:</p> <blockquote> <p>I suggest that $L$ should be uniformly distributed over all lines that intersect $[0,1]^n$ . It is not equivalent to the current distribution because with uniform distribution if you know the first intersection point is close to a corner, then the second intersection point is also more likely to be close to that corner.</p> </blockquote></li> </ol> <hr> <p><em>I guess this formulation is clearer than the old one. So if you can understand my question by reading above, please ignore everything I wrote below.</em></p> <hr> <h2>Old formulation: a messy one</h2> <p>I'll first describe how I divide $\mathbb{R}^{n}$ into $K$ convex sets, then describe my problem.</p> <p>First of all, I define a function $\mathcal{C}(\mathbf{x}): \mathbb{R}^{n}\mapsto \{1,\ldots,K\}$ as follows:</p> <p>$\mathcal{C}(\mathbf{x})=\underset{k=1,\ldots,K}{\mathrm{sargmax}} \mathbf{w}_{k}^{T}\mathbf{x}$,</p> <p>where sargmax denotes the maximizer with the smallest $k$ value. Moreover, define</p> <p>$S_{k}=\{\mathbf{x}\in \mathbb{R}^{n}|\mathcal{C}(\mathbf{x})=k\}$,</p> <p>where $k\in\{1,\ldots,K\}$.</p> <p>The following statements can be easily proved.</p> <p>-The collection $S_{1},S_{2},\ldots,S_{K}$ forms a partition of $\mathbb{R}^{n}$.</p> <p>-$\forall k\in\{1,\ldots,K\}$, $S_{k}$ is a convex set.</p> <p>For a line $L$ in $\mathbb{R}^{n}$, let</p> <p>$V=\{k\in\{1,\ldots,K\}|L\cap S_{k}\neq \emptyset\}$.</p> <p>A <em>random</em> line in $\mathbb{R}^n$ is a line connecting two points sampled from a $n$-dimensional normal distribution.</p> <h3>Here comes my question:</h3> <p>Assume that $\mathbf{w}_1,\ldots, \mathbf{w}_K$ are iid random variables in $\mathbb{R}^n$, each $\mathbf{w}_i \sim \mathcal{N}_n(\mu, \Sigma)$. For a random line $L$ in $\mathbb{R}^{n}$, what is the expected value of $|V|$?</p> <p>It would be also nice if someone could re-formulate this problem into a less cumbersome one, or perhaps point me to some literature about this problem.</p> http://mathoverflow.net/questions/80242/complexity-of-detecting-a-convex-body-in-mathbbrn/80317#80317 Comment by han han 2011-11-08T13:36:20Z 2011-11-08T13:36:20Z @Joel David Hamkins Thanks for your very detailed answer. Indeed, my problem formulation on $\mathbb{R}^n$ is problematic and imprecise. Thanks for pointing it out. I'm glad to see your first two theorems are established by restricting $\mathbb{R}^n$ to a countable dense set, which is what I meant. http://mathoverflow.net/questions/80242/complexity-of-detecting-a-convex-body-in-mathbbrn Comment by han han 2011-11-07T16:07:40Z 2011-11-07T16:07:40Z @Robert Israel and @Igor Rivin: Thanks for the remark. I've updated my question accordingly. http://mathoverflow.net/questions/76486/measure-of-the-set-of-lines-that-intersect-a-bounded-convex-set-k-in-mathbbr/76488#76488 Comment by han han 2011-09-27T11:21:29Z 2011-09-27T11:21:29Z Thanks for providing a reference. http://mathoverflow.net/questions/76486/measure-of-the-set-of-lines-that-intersect-a-bounded-convex-set-k-in-mathbbr Comment by han han 2011-09-27T11:18:03Z 2011-09-27T11:18:03Z Sorry if this problem waste your time. I did carefully read Chapter 1-6 including every notes, remarks and exercises he made. Yet I haven't found the generalised version of this result. I guess I have to find the answer in other chapters. Thanks Gjergji Zaimi for providing a reference. http://mathoverflow.net/questions/76345/upper-and-lower-bounds-of-the-total-surface-area-of-convex-polytopes-that-partiti Comment by han han 2011-09-26T15:18:03Z 2011-09-26T15:18:03Z Thanks Anton Petrunin and Ilya Bogdanov for the nice answer and explanation. To complete the answer, the maximal area of the intersection of a $D$-cube with a $(D-1)$-dimensional hyper plane is $\sqrt{2}L^{D-1}$, where $L$ is the edge length of hypercube. <a href="http://www.jstor.org/stable/2046239" rel="nofollow">jstor.org/stable/2046239</a> http://mathoverflow.net/questions/75413/angle-btween-coordinate-vector-and-normal-vector-of-facet-in-a-convex-polytope-a/75432#75432 Comment by han han 2011-09-15T09:55:55Z 2011-09-15T09:55:55Z Thanks Ilya Bogdanov for this nice and clear solution. http://mathoverflow.net/questions/73511/draw-a-random-line-through-a-voronoi-tessellation-what-is-the-average-number-of/73561#73561 Comment by han han 2011-09-14T13:01:19Z 2011-09-14T13:01:19Z It takes me some time to understand the result. While searching related literatures, I found this &quot;Integral geometry and geometric probability By Luis Antonio Santal&#243;, pp71&quot; <a href="http://books.google.com/books?id=anX4loxoYLwC&amp;lpg=PP1&amp;dq=Integral%20geometry%20and%20geometric%20probability&amp;pg=PA71#v=onepage&amp;q&amp;f=false" rel="nofollow">books.google.com/&hellip;</a> From my point of view, 'Remark''s answer looks like a generalised version of eq(5.10) in $\mathbb{R}^{n}$ when the breadth $a=0$. http://mathoverflow.net/questions/73511/draw-a-random-line-through-a-voronoi-tessellation-what-is-the-average-number-of/73658#73658 Comment by han han 2011-08-26T15:51:56Z 2011-08-26T15:51:56Z I just realised that most published results give $\mathbb{E}|T|$ when K is infinity, whereas I'm mostly interested in a convex ploytope tessellation with small number of cells. So maybe this changes everything, what if I want to find $\mathbb{E}F$ when the number of cells $K$ is small, e.g. $K&lt;50$. In particular, is there a way to write $\mathbb{E}F$ as a function (or approximated function) of $n$, dimension of space and $K$, the number of cells? http://mathoverflow.net/questions/73511/draw-a-random-line-through-a-voronoi-tessellation-what-is-the-average-number-of/73658#73658 Comment by han han 2011-08-26T04:48:03Z 2011-08-26T04:48:03Z Thanks for your information. I also found [this document] (<a href="http://algo.inria.fr/csolve/vi.pdf" rel="nofollow">algo.inria.fr/csolve/vi.pdf</a>) which summaries useful statistics for Poisson-Voronoi Tessellations on $R^1$, $R^2$ and $R^3$. I haven't found any result about $(n-1)$-dimensional measure of the facets of the tessellation. Nevertheless, there are bunch of software can give asymptotic statistics by simulation, e.g. [Qhull](<a href="http://www.qhull.org/" rel="nofollow">qhull.org</a>) http://mathoverflow.net/questions/73511/draw-a-random-line-through-a-voronoi-tessellation-what-is-the-average-number-of/73561#73561 Comment by han han 2011-08-25T07:15:59Z 2011-08-25T07:15:59Z Thanks for a very detailed answer. As the problem now becomes finding $E|T|$, I'm searching some literatures about the general result on a convex polytopes tessellation. Thanks for your help again. Furthermore, as you mentioned it in the end, I'd like to know more about restricting $L$ to axis-aligned lines. http://mathoverflow.net/questions/73511/draw-a-random-line-through-a-voronoi-tessellation-what-is-the-average-number-of Comment by han han 2011-08-24T10:55:36Z 2011-08-24T10:55:36Z Thanks Remark for pointing out the inappropriate distribution of $L$ in this question. http://mathoverflow.net/questions/73511/draw-a-random-line-through-a-voronoi-tessellation-what-is-the-average-number-of Comment by han han 2011-08-24T06:12:21Z 2011-08-24T06:12:21Z Thanks Anthony Quas for point out the possibility of a further reformulation. I will try to restate my problem using homogeneous Poisson point processes in the next few hours. http://mathoverflow.net/questions/73511/draw-a-random-line-through-a-voronoi-tessellation-what-is-the-average-number-of Comment by han han 2011-08-24T00:42:58Z 2011-08-24T00:42:58Z Thanks Joseph O'Rourke for the reference. I also found my problem formulation cumbersome. I will try to restate my problem in a clearer way in the next few minutes. http://mathoverflow.net/questions/73511/draw-a-random-line-through-a-voronoi-tessellation-what-is-the-average-number-of Comment by han han 2011-08-23T22:37:51Z 2011-08-23T22:37:51Z Thanks Anton Geraschenko for point out the typo in my question. Regarding the distribution of $\mathbf{w}_1,\ldots,\mathbf{w}_K$, let's assume it is normally distributed and independent. Finally, thanks for your reference of Voronoi diagram. I'll google it and see if I can get something useful there.