It is well known that the circumcenter of a polygon exists if and only if the polygon is cyclic.

I would like to extend the definition of an circumcenter for noncyclic polygons. Namely, let us define the least squares circumcenter as the point A$(x_0, y_0)$ such that the point A minimizes the sum of the squares of the residuals.

Let us consider the case for a noncyclic quadrilateral with vertices P$(x_1, y_1)$, Q$(x_2, y_2)$, R$(x_3, y_3)$, and S$(x_4, y_4)$. Let us also define the origin O$(0, 0)$.

How would we solve for the point A in this case? I was thinking of using matrices and solving $A^\mathsf{T}A \hat{x} = A^\mathsf{T}b$, although any methods are welcome.

  • $\begingroup$ Are you asking about how to set up the least squares problem, or how to solve it once you have it? Forming and solving the normal equations directly is numerically unstable. $\endgroup$ – tch Dec 26 '18 at 18:17
  • $\begingroup$ @TylerChen My question is asking for the least squares solution to the circumcenter, in closed form. I don't have a background in least squares but any methods are acceptable as long as they yield the correct answer. Thanks. $\endgroup$ – pacosta Dec 26 '18 at 18:41
  • $\begingroup$ Thanks for the update! When you say residual, do you mean the difference between he center point and vertices? $\endgroup$ – tch Dec 26 '18 at 18:44
  • 1
    $\begingroup$ As a general observation: if you are trying to generalize a concept to a broader class of examples, you usually want to argue that the generalization reduces to the original notion where the original notion was defined. What property of the incenter (or perhaps circumcenter) was it you were hoping to generalize? As an example: you could seek the circle which best fits the vertices (minimizing least square distance to the vertices, say) and define the generalized circumcenter as the center of that circle, trusting it is unique. That gives the actual circumcenter whenever there is one. $\endgroup$ – lulu Dec 26 '18 at 19:18
  • 1
    $\begingroup$ @lulu 's interpretation of the question as asking for the center of the best-fit circle seems like the only sensible interpretation of the question that I can see. See the 2000 paper "A Few Methods for Fitting Circles to Data" by Umbach and Jones, which calls this the "Full Least Squares Method" (FLS) and compares it to four other alternative definitions. $\endgroup$ – Don Hatch Jun 6 at 23:47

Suppose the polygon has vertices $P_1,\ldots, P_m \in\mathbb{R}^n$. The distance $d_i$ from a point $x$ to $P_i$ is simply $d_i = \lVert{P_i-x}\rVert_2$. We would like to minimize the sum of squares of distances. That is, find $x$ solving: $$ \min_x \sum_{i=1}^{m} d_i^2 = \min_x \sum_{i=1}^{m} \lVert P_i-x\rVert_2^2 $$

Consider the square of the 2-norm of the block matrix of size $mn\times 1$ (tall vector), $$ \begin{bmatrix} P_1-x \\ P_2-x \\ \vdots \\ P_m-x \end{bmatrix} $$

The square of the 2-norm of this matrix is exactly $\sum_i d_i^2$. To see this note that d_i^2 is the sum of squares of the entries in the vector $P_i-x$ so that $\sum_i d_i^2$ is the sum of squares of the entries in $P_i-x$ for all $i$.

We can rewrite this matrix in the form $b-Ax$, $$ \begin{bmatrix} P_1-x \\ P_2-x \\ \vdots \\ P_m-x \end{bmatrix} = \begin{bmatrix} P_1\\ P_2 \\ \vdots \\ P_m \end{bmatrix} - \begin{bmatrix} I \\ I \\ \vdots \\ I \end{bmatrix} x $$ where $I$ is the $n\times n$ identity.

To find $x$ we then solve the least squares problem $\min_x \lVert b-Ax \rVert_2$.

EDIT: to see that this just gives the average of the points, form the normal equations.

  • $\begingroup$ The question is unfortunately not as clear as it could be, but I believe what's being asked for is minimizing the sum of squares of deviations from the mean distance. That yields the circumcenter when there is one. You're minimizing the sum of squares of distances, which is a different problem. $\endgroup$ – Don Hatch May 30 at 20:31
  • $\begingroup$ Are the "residuals" in the original post not the same as the distances $d_i$? Based on one of the comments, the OP was trying to generalize the circumcenter of a triangle, which would be found using the method in this solution. $\endgroup$ – tch May 31 at 20:29
  • 1
    $\begingroup$ In order to generalize circumcenter of a triangle, "residuals" would have to be interpreted as (something like) deviations from the mean distance, rather than the distances themselves. Note, your solution does not find the circumcenter of a triangle; your solution is actually a roundabout way of computing the centroid, i.e. average, of the vertices (try it!), which is a different thing. $\endgroup$ – Don Hatch Jun 1 at 0:41
  • $\begingroup$ Ah yes, good point. I think I understand now what the OP was asking. Is there a standard for whether to delete incorrect responses, or leave them? $\endgroup$ – tch Jun 1 at 2:31

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.