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



Euclidean neighborhoods on Polyhedral surface
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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.8591),"
*Discrete & Comptuational Geometry*, Vol. 39, March 2008, 500-579.
* Yevgeny Schreiber, "[Shortest paths on realistic polyhedra](http://dl.acm.org/citation.cfm?id=1247081),"
Proceedings of the 23rd Annual Symposium on Computational Geometry, 2007.


