Euclidean neighborhoods on Polyhedral surface

2011-11-18T11:25:53Z

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

Answer by Joseph O'Rourke for Euclidean neighborhoods on Polyhedral surface

2011-11-29T16:14:51Z

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.

Euclidean neighborhoods on Polyhedral surface - MathOverflow

Euclidean neighborhoods on Polyhedral surface

Answer by Joseph O'Rourke for Euclidean neighborhoods on Polyhedral surface