Euclidean neighborhoods on Polyhedral surface - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T06:47:20Z http://mathoverflow.net/feeds/question/81243 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81243/euclidean-neighborhoods-on-polyhedral-surface Euclidean neighborhoods on Polyhedral surface acmath 2011-11-18T11:25:53Z 2011-11-29T16:20:41Z <p>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,</p> <p>that is, there exist </p> <p>$x_+ \in Adjacent(x)$ such that $(d ( x_+,x_0) - \epsilon ) > 0$, ( i.e. that lays outside $\mathcal{B}_\epsilon(x0)$) and</p> <p>at least two $x_- \in Adjacent(x)$ such that $(d ( x_-,x_0) - \epsilon ) &lt; 0$. (i.e. that lays inside $\mathcal{B}_\epsilon(x_0)$).</p> <p>$d$ being the euclidean distance, $x \in Vertex(X)$ , $Adjacent(x)$ vertices adjacent to x ( connected to x by an edge in X )</p> <p>Is there any algorithm to optimize the search for such x on $X$? </p> <p>I tried the $NN$ algorithm with Fixed radius to search for $\mathcal{B}_\epsilon(x_0)$. </p> <p>Is there any algorithm to optimize the search for the boundary of $\mathcal{B}_\epsilon(x_0)$?</p> <p>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)$. </p> <p>Also, may I use someway the graph structure on $X$? </p> http://mathoverflow.net/questions/81243/euclidean-neighborhoods-on-polyhedral-surface/82187#82187 Answer by Joseph O'Rourke for Euclidean neighborhoods on Polyhedral surface Joseph O'Rourke 2011-11-29T16:14:51Z 2011-11-29T16:20:41Z <p>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$.</p> <p>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$).</p> <ul> <li><p>Yevgeny Schreiber and Micha Sharir "<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.8591" rel="nofollow">An optimal-time algorithm for shortest paths on a convex polytope in three dimensions</a>," <em>Discrete &amp; Comptuational Geometry</em>, Vol. 39, March 2008, 500-579.</p></li> <li><p>Yevgeny Schreiber, "<a href="http://dl.acm.org/citation.cfm?id=1247081" rel="nofollow">Shortest paths on realistic polyhedra</a>," Proceedings of the 23rd Annual Symposium on Computational Geometry, 2007.</p></li> </ul>