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$? 
 A: 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$).


*

*Yevgeny Schreiber and Micha Sharir 
"An optimal-time algorithm for shortest paths on a convex polytope in three dimensions,"
Discrete & Comptuational Geometry, Vol. 39, March 2008, 500-579.

*Yevgeny Schreiber, "Shortest paths on realistic polyhedra,"
Proceedings of the 23rd Annual Symposium on Computational Geometry, 2007.
