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?

hotonglamoz 2022-09-16 Answered
Least Squares Circumcenter of Polygons
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 T A x ^ = A T b, although any methods are welcome.
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Mario Dorsey
Answered 2022-09-17 Author has 12 answers
Step 1
Suppose the polygon has vertices P 1 , , P m R n . The distance d i from a point x to P i is simply d i = P i x 2 . We would like to minimize the sum of squares of distances. That is, find x solving:
min x i = 1 m d i 2 = min x i = 1 m P i x 2 2
Consider the square of the 2-norm of the block matrix of size m n × 1 (tall vector),
[ P 1 x P 2 x P m x ]
Step 2
The square of the 2-norm of this matrix is exactly 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 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 A x,
[ P 1 x P 2 x P m x ] = [ P 1 P 2 P m ] [ I I I ] x
where I is the n × n identity.
To find x we then solve the least squares problem min x b A x 2 .
EDIT: to see that this just gives the average of the points, form the normal equations.

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-08-05
The area of a triangular sail for a boat is 176 square feel. If the base of the sail is 16 feet long, find its height.
asked 2022-07-16
Polygons with two different angles
I have the following questions:
Let us consider polygons with only two different interior angles α and β = π α.
For which frequencies of these angles is it possible to form a closed polygon?
asked 2022-08-11
Scan line algorithm for intersecting polygons
Given two sets of polygons P 1 = { s 1 , . . . , s m } and P 2 = { s m + 1 , . . . , s n } with total number of n segments, the previous and next segment on it's polygon can be determined in O(1). Describe a scan-line algorithm that computes all points of P 1 P 2 in O(n).
asked 2022-09-27
Minkowski difference of two convex polygons
I just want to make sure that the following algorithm is correct for computing the Minkowski difference of two shapes A,B:
Minkowski ( A , B ) =  CH  { x : x = a b  for  a A , b B }
Where CH(S) is the convex hull of the set S and a,b are the vertices of the two polygons.
asked 2022-08-22
Question regarding polygons
Can you prove, that if a equilateral lattice n-gon is constructible, then there will be such a polygon for which the sides have minimal length?
asked 2022-08-11
Constructible polygons
I know certain polygons can be constructed while others cannot. Here is Gauss' Theorem on Constructions:
cos ( 2 π / n ) is constructible iff n = 2 r p 1 p 2 · · · p k , where each p i is a Fermat prime.
Can this is be used to determine the constructibility of a regular p 2 polygon? If so how and what would be the cos ( 2 π / n ) here?
asked 2022-08-05
The area of a triangular sail for a boat is 176 square feel. If the base of the sail is 16 feet long, find its height.

New questions