1
$\begingroup$

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

$\endgroup$
7
  • 4
    $\begingroup$ I think that if you don't use Tex, you won't get an answer, since anybody quit readinig after two lines. $\endgroup$ Nov 18, 2011 at 12:49
  • $\begingroup$ Consider posting at math.stackexchange.com/questions?sort=newest but first, please read tea.mathoverflow.net/discussion/1125/… $\endgroup$
    – Will Jagy
    Nov 18, 2011 at 19:09
  • $\begingroup$ @Valerio Capraro. Thanks, I restored Tex $\endgroup$
    – acmath
    Nov 18, 2011 at 23:09
  • $\begingroup$ 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? $\endgroup$ Nov 28, 2011 at 18:57
  • $\begingroup$ 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. $\endgroup$ Nov 28, 2011 at 19:12

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.