MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $(X, Vertex(X))$ be a Polyhedral surface (defined like in Polthier) , $x_0 \in X$ a vertex. Let $B_\epsilon(x_0)$ the euclidean ball centred at $x_0$ with radius $\epsilon$, $\epsilon > max length(e), e \in edge(X) $. Define $\mathcal{B}_ \epsilon(x_0)$ the intersection of $B_\epsilon(x_0)$ with $X$ to be the euclidean neighborhood of $x_0$ on $X$. Define the $boundary$ as the set of all vertices $ x \in \mathcal{B}_ \epsilon(x_0)$ satisfying the following condition (1) : the function $ (d ( x,x_0) - \epsilon ) $ changes sign,

that is, there exist

$x_+ \in Adjacent(x)$ such that $(d ( x_+,x_0) - \epsilon ) > 0$, ( i.e. that lays outside $\mathcal{B}_\epsilon(x0)$) and

at least two $x_- \in Adjacent(x)$ such that $(d ( x_-,x_0) - \epsilon ) < 0$. (i.e. that lays inside $\mathcal{B}_\epsilon(x_0)$).

$d$ being the euclidean distance, $x \in Vertex(X)$ , $Adjacent(x)$ vertices adjacent to x ( connected to x by an edge in X )

Is there any algorithm to optimize the search for such x on $X$?

I tried the $NN$ algorithm with Fixed radius to search for $\mathcal{B}_\epsilon(x_0)$.

Is there any algorithm to optimize the search for the boundary of $\mathcal{B}_\epsilon(x_0)$?

I tried to define an alogrithm that starts from $x_{max}$ (a point of maximum of $d(-,x_0)$ in $\mathcal{B}_\epsilon(x_0) : d(y,x_0) \leq d(x_{max},x_0) , y \neq x, y \in \mathcal{B}_\epsilon(x_0)$ ) and define boundary points by adjacency with check condition given in (1). This shoud give a closed path $x_{max} \leadsto x_{max}$ that minimizes the distance from the boundary of $B_\epsilon(x0)$.

Also, may I use someway the graph structure on $X$?

share|cite|improve this question
I think that if you don't use Tex, you won't get an answer, since anybody quit readinig after two lines. – Valerio Capraro Nov 18 '11 at 12:49
Consider posting at but first, please read… – Will Jagy Nov 18 '11 at 19:09
@Valerio Capraro. Thanks, I restored Tex – acmath Nov 18 '11 at 23:09
Are both $\epsilon$ and $x_0$ fixed, i.e., do you want to find $\cal{B}_\epsilon(x_0)$ when those two parameters are fixed? And roughly how many vertices $n$ are on the surface? – Joseph O'Rourke Nov 28 '11 at 18:57
As I read your definitions, sometimes $\cal{B}_\epsilon(x_0)$ is empty; is this correct? E.g., Let $X$ be a unit cube, and $\epsilon=\frac{1}{2}$. Then the boundary is empty, because although there are 7 vertices outside the ball at one corner, there are not at least two $x_-$ inside. – Joseph O'Rourke Nov 28 '11 at 19:12
up vote 0 down vote accepted

My hunch is that it is difficult to exploit the structure of the 1-skeleton of your polyhedral surface $\partial P$ to gain efficiency, especially in view of your $n$ only being on the order of $10^3$. I suspect efficiencies might only kick in for much larger $n$.

If you nevertheless want to explore options, I recommend you look at the paper by Schreiber and Sharir listed below. The first two steps in their (many-step) algorithm is to construct an oct-tree subdivision on the vertices of $\partial P$, and then from that build a "conforming surface subdivision" of $\partial P$. It is this data structure that permits them to achieve $O(n \log n)$ time for their task (which is not the same as your task). Schreiber extended this work to certain nonconvex polyhedra, which is presumably your situation (since you don't mention convexity); see the second paper below. I think a conforming surface subdivision data structure might speed your search (for large $n$).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.