Hot answers tagged

1

Compute the Voronoi Diagram of your point set. The center of the largest inscribed circle will be on one of the (linearly many) Voronoi nodes. To compute the VD, you could for instance use CGAL.


1

Think of $X = x p + (1-x) q = q + x (p - q)$ as the parametric equation of a point $X$. It is obtained by starting at $q$ and moving parallel to the vector $p-q$. Thus this is the parametric equation of a straight line. At $x = 0$ you get $X=q$, at $x=1$ you get $X=p$, so it's the straight line through points $p$ and $q$. As $x$ goes from $0$ to $1$, ...


1

In your example $p = (1,2)$ and $q = (3,4)$, $r = (2.5,3)$ is not a convex combination. By solving for $x$, in the first coordinate, we get $$3x - 1(1-x) = 2.5 \Rightarrow x = \frac{7}{8}$$ but in the second coordinate $$ 4x - 2(1-x) = 3 \Rightarrow x = \frac{5}{6} $$ It follows that $r \notin \text{conv}(p \cup q) = \lbrace s : s = \lambda p + (1 - \lambda)...


1

Here's what a correct Voronoi tesselation looks like:


1

This is a special case of computing the distance between two convex sets (a point by itself is a convex set). This paper A fast procedure for computing the distance between complex objects in three-dimensional space was brought to my attention by Joseph O'Rourke and it references an $\mathcal{O}(\log M)$ algorithm for the two dimensional case. Here $M$ is ...


1

If the convex polygon is represented by the intersection of finitely many half-planes $$P := \{ x \in \mathbb R^2 \mid A x \leq b \}$$ then we can find the point $x^* \in P$ closest to a given $y \in \mathbb R^2$ by solving the quadratic program $$\begin{array}{ll} \text{minimize} & \|x - y\|_2^2\\ \text{subject to} & A x \leq b \end{array}$$ If ...


1

You could do something that is somewhat like binary search indeed: To find the closest point on $P_1P_2P_3\ldots P_n$, find the closest point on $P_1P_3P_5\ldots P_{\lceil n/2\rceil}$. If it is between $P_k$ and $P_{k+2}$ then we need only test vertex $P_{k+1}$ and its adjacent edges for the original polygon. If it is exactly at $P_k$, we also need only ...



Only top voted, non community-wiki answers of a minimum length are eligible