I am searching for the correct term for the following, if it exists.

A set $X\subset \mathbb{R}^2$ is called $r$-convex if for any two points $x_1, x_2\in X$ such that there exists an arc of radius $r$ connecting these two points, at least one arc lies in the set $X$.

Note 1: Obviously, there are always two arcs of radius $r$ (if one exists) connecting two points.

Note 2: When $r\rightarrow +\infty$ we have the definition of convex set.

My main interest is efficient algorithms for computation of convex hulls based on this definition of convexity.

  • 1
    $\begingroup$ I think I would disagree with your first note as, surely, if we take the set X to be a semicircle of radius r then there is only one arc of radius r between any two points. $\endgroup$ – Stijn Apr 18 '14 at 12:56
  • $\begingroup$ @Stijn, I think he's saying that there are two arcs in $\mathbb{R}^2$, not necessarily in $X$. $\endgroup$ – Dylan Thurston Apr 18 '14 at 14:20
  • $\begingroup$ It seems like a weird notion. Where does it come up? $\endgroup$ – Dylan Thurston Apr 18 '14 at 14:20
  • $\begingroup$ Yes, I am talking about two arcs in $\mathbb{R}^2$. $\endgroup$ – Fedor Nikitin Apr 18 '14 at 14:27
  • $\begingroup$ @Dylan At the moment I am working on algorithm for rounding sharp corners in polygon. Let $P$ be a set of points lying in polygon. I need to find $P^\prime$ such that its border consists of segments and arcs. Arc radius should not exceed $r$ and there are no sharp angles (less than $\pi$). I have guess that $P\prime = \mathbb{R}^2 \ co_r (\mathbb{R}^2 \ P)$, where $co_r$ is convex hull in the sense of definition above. My idea is to apply algorithms for regular convex hull with modified definition of convexity. $\endgroup$ – Fedor Nikitin Apr 18 '14 at 14:40

I can not comment posts because of too small reputation :-) It will change I hope.

In connection with usul's comment:

Also strongly convex sets are considered. Roughly speaking, one could require that together with two points the whole lens is contained in a set. For a definition see for instance here: http://arxiv.org/pdf/1207.4347.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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