# Euclidean neighborhoods on Polyhedral surface

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

-
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 math.stackexchange.com/questions?sort=newest but first, please read tea.mathoverflow.net/discussion/1125/… – 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

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