2
$\begingroup$

What algorithms currently exist to determine the convex kernel of any low-dimensional set, especially a planar set? Also, if one exists, what research has been done on it and are there any references with which you could supply me?

Thanks

  • 0
    Do you mean http://en.wikipedia.org/wiki/Convex_hull_algorithms ?2012-03-13
  • 0
    Thank you for that comment, I meant the convex kernel, not the hull. I edited it. And will do.2012-03-13
  • 1
    This paper seems relevant: Lee and Preparata, "An optimal algorithm for finding the kernel of a polygon", JACM 26.3 (1979), [doi:10.1145/322139.322142](http://dx.doi.org/10.1145/322139.322142)2012-03-18
  • 0
    I think that to generate answers it would be wise to define the terms you have in your question. A star-shaped set $S$ is a subset of $\mathbb R^n$ for which there exists an $x_0 \in S$ with the property that for all $x \in S$, the line between $x_0$ and $x$ lies in $S$. The convex kernel of $S$ is the set of all $x_0$'s which makes $S$ into a star-shaped set. (Am I correct? I found this by googling.)2012-03-18
  • 0
    @StevenTaschuk: You should upgrade your comment to an answer.2012-03-18
  • 0
    @JeffE: Ok, done.2012-03-18
  • 0
    @PatrickDaSilva Yes, you are essentially right. More specifically, the convex kernel of a set V is the set of all x such that for any y in V, the line between x and y is in V.2012-03-19

1 Answers 1