User han - MathOverflow

Complexity of detecting a convex body in $\mathbb{R}^n$?

2011-11-06T20:57:30Z

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,

$K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
The boundary between $K_1$ and $K_2$ is unknown. (To avoid the trivial case, I assume that the boundary is not a hyperplane.)
Either $K_1$ or $K_2$ is a convex set, but we don't know which one is.
We have two initial points $\mathbf{x},\mathbf{y}$ on hand, where $\mathbf{x}\in K_1$ and $\mathbf{y}\in K_2$.

Essentially, $K_0$ can be viewed as a black box. Further assume that one can query any point in $K_0$ with a membership oracle, namely a procedure that given a point $\mathbf{p}\in K_0$, reports the set contains $\mathbf{p}$.

The goal is to determine which set is convex using membership queries.

My questions:

Can this be done with finite number of queries?
What is the complexity class of this problem?

Thanks.

Upper and Lower Bounds of the Total Surface Area of Convex Polytopes that Partition a Hypercube

2011-09-25T16:41:22Z

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$.

In case it is not clear, the surface area of a convex polytope $\mathcal{P}$ is the sum of $(D-1)$-dimensional Lebesgue measure of the facets of $\mathcal{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< K<50$.
I guess this problem has been solved, but I'm struggling to find good literature.

Angle btween Coordinate Vector and Normal Vector of Facet in a Convex Polytope, Asking for a Counterexample

2011-09-14T15:28:28Z

Definitions

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})$.

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\}$.

Let $\mathbf{p}=(p_{1},\ldots,p_{D})$ be a point in $\mathbb{R}^{D}$. Define

$L_{d}=\{\mathbf{p}+\theta\mathbf{u}_{d}|\theta\in \mathbb{R}\},$

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.

For $k=1,\ldots, K$, define

$G_{k}=\{d|L_{d}\cap F_{k}\neq \emptyset\}.$

Define $f:\mathbb{R}^{D}\times\mathbb{R}^{D}\rightarrow [0,1]$ as

$f(\mathbf{x},\mathbf{y})=\frac{|\mathbf{x}^\mathrm{T}\mathbf{y}|}{\left\|\mathbf{x}\right\|\left\|\mathbf{y}\right\|}.$

My conjecture

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})\}$.

Can anyone provide a counterexample?

An illustrative example in $\mathbb{R}^2$

In particular, if we restrict ourself in $\mathbb{R}^2$, the above conjecture can be restated as follows:

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°.

The figure below gives an example.

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.

Finally, any problem reformulation is also welcome.

Draw a Random Line Through a Voronoi Tessellation, What is the Average Number of Voronoi Cell the Line Intersects?

2011-08-23T17:17:45Z

Update: problem reformulation

Following the advice in comments, I now restate my problem using Voronoi tessellation.

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.

Let $V_k$ be the $k$-th Voronoi cell. Define

$\mathcal{V}=\{k\in\{1,\ldots,K\}|L\cap V_{k}\neq \emptyset\}$,

where $L$ is a line that intersects $H_n$

My question

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?

Clarification of edits

In the last formulation, $K$ points were uniformly distributed on $[0,1]^n$. Anthony Quas suggests that using a Poisson point process is preferable.
My original definition of a random $L$ is: the end points of $L$ are uniformly distributed on $H_n$'s edges. However, in Remark's comment:

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.

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.

Old formulation: a messy one

I'll first describe how I divide $\mathbb{R}^{n}$ into $K$ convex sets, then describe my problem.

First of all, I define a function $\mathcal{C}(\mathbf{x}): \mathbb{R}^{n}\mapsto \{1,\ldots,K\}$ as follows:

$\mathcal{C}(\mathbf{x})=\underset{k=1,\ldots,K}{\mathrm{sargmax}} \mathbf{w}_{k}^{T}\mathbf{x}$,

where sargmax denotes the maximizer with the smallest $k$ value. Moreover, define

$S_{k}=\{\mathbf{x}\in \mathbb{R}^{n}|\mathcal{C}(\mathbf{x})=k\}$,

where $ k\in\{1,\ldots,K\}$.

The following statements can be easily proved.

-The collection $S_{1},S_{2},\ldots,S_{K}$ forms a partition of $\mathbb{R}^{n}$.

-$\forall k\in\{1,\ldots,K\}$, $S_{k}$ is a convex set.

For a line $L$ in $\mathbb{R}^{n}$, let

$V=\{k\in\{1,\ldots,K\}|L\cap S_{k}\neq \emptyset\}$.

A random line in $\mathbb{R}^n$ is a line connecting two points sampled from a $n$-dimensional normal distribution.

Here comes my question:

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|$?

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.

Comment by han

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.

Comment by han

2011-11-07T16:07:40Z

@Robert Israel and @Igor Rivin: Thanks for the remark. I've updated my question accordingly.

Comment by han

2011-09-27T11:21:29Z

Thanks for providing a reference.

Comment by han

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.

Comment by han

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. jstor.org/stable/2046239

Comment by han

2011-09-15T09:55:55Z

Thanks Ilya Bogdanov for this nice and clear solution.

Comment by han

2011-09-14T13:01:19Z

It takes me some time to understand the result. While searching related literatures, I found this "Integral geometry and geometric probability By Luis Antonio Santaló, pp71" books.google.com/… 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$.

Comment by han

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<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?

Comment by han

2011-08-26T04:48:03Z

Thanks for your information. I also found [this document] (algo.inria.fr/csolve/vi.pdf) 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](qhull.org)

Comment by han

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.

Comment by han

2011-08-24T10:55:36Z

Thanks Remark for pointing out the inappropriate distribution of $L$ in this question.

Comment by han

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.

Comment by han

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.

Comment by han

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.