5
\$\begingroup\$

Given is a grid polygon by the list of its integer vertex coordinates arranged along the perimeter, in the form

\$(x_1,y_1), (x_2,y_2), \cdots , (x_n,y_n)\$ with \$n \ge 3\$.

The polygon is completed by connecting point \$n\$ to point \$1\$.

For simplicity, it may be assumed that the polygon is simple and does not have interior angles \$\gt \pi\$.

The diameter D is defined here as the largest Euclidean distance between any two points on the circumference of the polygon.

A polygon can be deformed by applying shear while the area remains the same. The area \$A\$ of a polygon can be calculated in a known way, but it is not needed for the task at hand, because the area will not be changed by any shear.

See Wikipedia Shear Mapping.

Challenge

Your task is to create a function that, given a polygon, finds an arbitrary sequence of such shears so that the diameter d of the transformed polygon becomes as small as possible.

This is related to a question in mathoverflow and this challenge.

Only those shears should be considered that are parallel to the coordinate axes and that result in a polygon with integer coordinates, i.e., with integer, but potentially negative, \$m\$ in the transformation matrices

\$ \\ \begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} 1 & m \\ 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \hspace {3mm}or \hspace {3mm} \begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ m & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \$

The program shall return the value of the minimum possible squared diameter \$d^2\$ and the transformed vertex coordinates, such that \$min(x'_i) = min(y'_i) = 0\$.

The coordinates can be passed to the function in whatever form seems most appropriate, e.g., as a matrix or as vectors or as a reference to a data structure. It is permissible to overwrite the input coordinates in the result.

If it is possible in the selected language with little effort, then a framework program should be made available that reads and outputs the results in the following format:

\$(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\$

The commas between \$x\$ and \$y\$ and between \$),(\$ are mandatory. The calculated squared diameter shall also be output.

A framework program must not perform any pre- or post-processing other than reading and displaying the data and conversion to/from the required form for the transformation function.

The program should be able to handle polygons with at least 40 vertices.

This is Code Golf, i.e., the shortest code (in bytes) able to solve the problem wins. However, only the length of the transformation function is used for the Code Golf score.

The described form of output is chosen in order to be able to be used as input for a visualization program, e.g., Markus Sigg's PolygonalAreasViewer

Example

Input, a polygon with n=15 and D^2=2810:
(1,1),(3,2),(6,4),(16,11),(23,16),(34,24),(38,27),(43,31),(44,32),(42,31),(39,29),(32,24),(21,16),(6,5),(2,2)
First shear x' = x - y
d^2=1105: (0,1),(1,2),(2,4),( 5,11),( 7,16),(10,24),(11,27),(12,31),(12,32),(11,31),(10,29),( 8,24),( 5,16),(1,5),(0,2)
Second shear y' = y - 2*x'
d^2=193: (0,1),(1,0),(2,0),( 5, 1),( 7, 2),(10, 4),(11, 5),(12, 7),(12, 8),(11, 9),(10, 9),( 8, 8),( 5, 6),(1,3),(0,2)
Third shear: x'' = x' - y'
d^2=82: (-1,1),(1,0),(2,0),( 4, 1),( 5, 2),( 6, 4),( 6, 5),( 5, 7),( 4, 8),( 2, 9),( 1, 9),( 0, 8),(-1, 6),(-2,3),(-2,2)
No further reduction of diameter possible; normalize position x''' = x'' + 2, y''' = y'
Expected return value: 82 (=d^2) and coordinates printed: 
 (1,1),(3,0),(4,0),(6,1),(7,2),(8,4),(8,5),(7,7),(6,8),(4,9),(3,9),(2,8),(1,6),(0,3),(0,2)

Applied shears

Test Cases

n = 3
A=1/2, D^2=26: (0,0),(1,0),(5,1)
->     d^2= 2: (0,0),(1,0),(1,1)

A=1/2, D^2=74: (0,0),(3,2),(7,5)
->     d^2= 2: (0,0),(1,0),(1,1)

A=50, D^2=233: (-3,2),( 3,-2),(10,10)
->    d^2=169: ( 0,4),(10, 0),( 5,12) 

n = 7
A=6.5, D^2=13: (1,0),(2,0),(3,1),(3,2),(1,3),(0,3),(0,2)
->     d^2=13: (1,0),(2,0),(3,1),(3,2),(1,3),(0,3),(0,2)
               (input unchanged)

n = 8
A=7, D^2=149: (0,0),(1,1),(-1,0),(-4,-2),(-8,-5),(-9,-6),(-7,-5),(-4,-3)
->   d^2= 10: (3,1),(3,2),( 2,3),( 1, 3),( 0, 2),( 0, 1),( 1, 0),( 2, 0)

n = 15
A=51.5, D^2=18853: (0,0),(13,9),(36,25),(46,32),(43,30),(21,15),(2,2),(-14,-9),(-27,-18),(-50,-34),(-60,-41),(-67,-46),(-64,-44),(-45,-31),(-29,-20)
->      d^2=   82: (9,4),( 9,5),( 8, 7),( 7, 8),( 6, 8),( 3, 7),(1,6),(  0, 5),(  0,  4),(  1,  2),(  2,  1),(  4,  0),(  5,  0),(  7,  1),(  8,  2)

n = 17
A=75.5, D^2=1361: (1,-13),(1,-14),(2,-14),(3,-13),(6,-9),(8,-6),(13,2),(16,7),(20,14),(21,16),(21,17),(20,16),(17,12),(12, 5),(10, 2),(5,-6),(2,-11)
->      d^2= 137: (0,  7),(1,  5),(3,  2),(4,  1),(6, 0),(7, 0),( 9,1),(10,2),(11, 4),(11, 5),(10, 7),( 9, 8),( 7, 9),( 4,10),( 3,10),(1, 9),(0,  8)

n = 19
A=106.5, D^2=11240: (1,1),(2,2),(7,6),(11,9),(26,20),(37,28),(44,33),(61,45),(71,52),(84,61),(87,63),(86,62),(82,59),(67,48),(56,40),(38,27),(31,22),(14,10),(4,3)
->       d^2=  202: (2,3),(1,5),(0,8),( 0,9),( 1,11),( 2,12),( 3,12),( 6,11),( 8,10),(11, 8),(12, 7),(13, 5),(13, 4),(12, 2),(11, 1),( 9, 0),( 8, 0),( 5, 1),(3,2)

n = 20:
A=121: D^2=394: ( 0,0),( 1,0),( 2,1),( 2,2),( 1, 5),( 0, 7),(-2,10),(-3,11),(-6,13),(-8,14),(-11,15),(-12,15),(-13,14),(-13,13),(-12,10),(-11,8),(-9,5),(-8,4),(-5,2),(-3,1)
->     d^2=241: (13,4),(14,5),(15,7),(15,8),(14,10),(13,11),(11,12),(10,12),( 7,11),( 5,10),(  2, 8),(  1, 7),(  0, 5),(  0, 4),(  1, 2),(  2,1),( 4,0),( 5,0),( 8,1),(10,2)

n = 24:
A=260, D^2=937: ( 0, 0),( 2, 3),( 2, 4),(1, 5),(-1, 6),(-2, 6),(-5, 5),(-7, 4),(-10, 2),(-14,-1),(-15,-2),(-18,-6),(-20,-9),(-21,-11),(-22,-14),(-22,-15),(-21,-16),(-19,-17),(-18,-17),(-15,-16),(-13,-15),(-9,-12),(-8,-11),(-5,-7)
->     d^2=578: (13,17),(12,20),(11,21),(9,22),( 6,23),( 5,23),( 3,22),( 2,21),(  1,19),(  0,16),(  0,15),(  1,11),(  2, 8),(  3,  6),(  5,  3),(  6,  2),(  8,  1),( 11,  0),( 12,  0),( 14,  1),( 15,  2),(16,  5),(16,  6),(15,10)

A=238.5, D^2=657: (6,1),(5,1),(3,2),(2,3),(1, 5),(1, 6),(2,10),(3,13),(4,15),(6,18),(9,22),(10,23),(13,25),(14,25),(15,24),(16,22),(17,19),(17,17),(16,13),(15,10),(14,8),(12,5),(11,4),(8,2)
->       d^2=409: (5,2),(4,3),(2,6),(1,8),(0,11),(0,12),(1,15),(2,17),(3,18),(5,19),(8,20),( 9,20),(12,19),(13,18),(14,16),(15,13),(16, 9),(16, 7),(15, 4),(14, 2),(13,1),(11,0),(10,0),(7,1)

n = 27:
A=343.5, D^2=1233: ( 0,0),( 1,0),( 4,1),( 5,2),( 5,3),( 4,5),( 2,8),( 1,9),(-2,11),(-4,12),(-9,14),(-12,15),(-16,16),(-21,17),(-22,17),(-25,16),(-27,15),(-28,14),(-28,13),(-27,10),(-26,8),(-25,7),(-23,6),(-18,4),(-15,3),(-11,2),(-6,1)
->       d^2= 788: (18,0),(19,0),(23,1),(25,2),(26,3),(27,5),(28,8),(28,9),(27,11),(26,12),(23,14),( 21,15),( 18,16),( 14,17),( 13,17),(  9,16),(  6,15),(  4,14),(  3,13),(  1,10),(  0,8),(  0,7),(  1,6),(  4,4),  (6,3),  (9,2),(13,1)

n = 38:
A=360, D^2=71444: (1,1),(11,9),(21,19),(31,29),(41,39),(51,49),(61,59),(71,69),(81,79),(91,89),(101,99),(111,109),(121,119),(131,129),(141,139),(151,149),(161,159),(171,169),(181,179),(191,189),(181,181),(171,171),(161,161),(151,151),(141,141),(131,131),(121,121),(111,111),(101,101),(91,91),(81,81),(71,71),(61,61),(51,51),(41,41),(31,31),(21,21),(11,11)
->     d^2=32404: (0,0),( 2,0),( 2,10),( 2,20),( 2,30),( 2,40),( 2,50),( 2,60),( 2,70),( 2,80),( 2, 90),(  2,100),(  2,110),(  2,120),(  2,130),(  2,140),(  2,150),(  2,160),(  2,170),(  2,180),(  0,180),(  0,170),(  0,160),(  0,150),(  0,140),(  0,130),(  0,120),(  0,110),(  0,100),( 0,90),( 0,80),( 0,70),( 0,60),( 0,50),( 0,40),( 0,30),( 0,20),( 0,10)
\$\endgroup\$
9
  • \$\begingroup\$ To clarify: when you say the largest Euclidean distance between any two points on the circumference of the polygon, do you mean on the permiter of the polygon? \$\endgroup\$
    – Luis Mendo
    Nov 19, 2022 at 23:11
  • \$\begingroup\$ Yes, points on the perimeter of the polygon. See, e.g., cgm.cs.mcgill.ca/~athens/cs507/Projects/2000/MS/diameter/… . \$\endgroup\$ Nov 20, 2022 at 4:22
  • \$\begingroup\$ I suggest removing this strict output formatting "in this format. The commas between x and y and between \$),(\$ are mandatory" as it is not core to the challenge. \$\endgroup\$ Nov 20, 2022 at 12:26
  • \$\begingroup\$ Also, why are we required to output the square - that seems like unnecessary fluff. \$\endgroup\$ Nov 20, 2022 at 12:33
  • 1
    \$\begingroup\$ I see that you want us to do our golf AND provide a program that wraps our golf. I don't think you should do that. \$\endgroup\$ Nov 20, 2022 at 12:37

2 Answers 2

2
\$\begingroup\$

PARI/GP 290 bytes

d(x,y)=C=0;for(i=1,#x,for(j=1,i,C=max(C,(x[i]-x[j])^2+(y[i]-y[j])^2)));C
shear(x,y)=T=D=d(x,y);until(T==D,T=D;if((t=d(x,z=y-x))<D,,if((t=d(x,z=y+x))<D));if(t<T,D=t;y=z);if((t=d(z=x-y,y))<D,,if((t=d(z=x+y,y))<D));if(t<D,D=t;x=z));for(k=1,#x,print1("("x[k]-vecmin(x)","y[k]-vecmin(y)"),"));D

The function \$shear(x,y)\$ has the coordinates, stored in 2 separate vectors, as arguments. Its return value is the squared diameter \$d^2\$. The transformed coordinates are written to output in the suggested format. The function \$d(x,y)\$ calculates the squared diameter.

Without any significant efforts regarding "golfing"; only to demonstrate the feasibility.

Auxiliary functions to read input

readc()={my(s="");
s=strjoin(strsplit(input(),"),("),";");
s=strjoin(strsplit(s,"("),"v=[");
s=strjoin(strsplit(s,")"),"]");
eval(s)};
inpgon()={my(mxy=readc());x=mxy[,1];y=mxy[,2];d(x,y)};

Example

inpgon()  \\ expects coordinate input from terminal delimited by "..."
"(1,1),(3,2),(6,4),(16,11),(23,16),(34,24),(38,27),(43,31),(44,32),(42,31),(39,29),(32,24),(21,16),(6,5),(2,2)"
2810  \\ returns D^2 of input

shear(x,y)  \\ call of function, prints result and returns d^2
(1,1),(3,0),(4,0),(6,1),(7,2),(8,4),(8,5),(7,7),(6,8),(4,9),(3,9),(2,8),(1,6),(0,3),(0,2),
82
\$\endgroup\$
1
\$\begingroup\$

R, 143 bytes

f=\(x,`+`=\(y)max(dist(y)^2)){d=+x;for(i in 2:3)for(j in -1:1){h=0
while(+x>+{h=h-1;m=diag(2);m[i]=j*h;y=x%*%m})x=y}
`if`(d>+x,f(x),list(d,x))}

Attempt This Online!

Recursively searches for the next best shear until further reduction in diameter cannot be found. Diameter calculation function is overloaded as + operator. Input and output of coordinates is by n x 2 matrix, transformation to required format is done in the footer. Note that output coordinates do not exactly match the provided test cases, but the diameters match and the shapes look the same.

\$\endgroup\$
1
  • \$\begingroup\$ Deviations in the coordinate list are OK as long as the minimum diameter is reached. The shearing sometimes has more than one result. Also happens with my PARI code. \$\endgroup\$ Nov 25, 2022 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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