0

2D Euclidean geometry. I'm not sure if this problem was already asked I tried to search but I failed to find similar. So imagine we have 4 randomly placed points on a plane. And we also have 4 identical rectangles that are "parallel" - i.e. their rotation is the same, for simplicity their long sides are all parallel to x-axis. A rectangle must be placed in such a way that only one of it's corners would touch only one of those 4 points(each rectangle would have it's own point). No 2 rectangles can overlap(but they may touch - e.g. if all 4 points happen to be in the same place). I suspect that we can always place 4 rectangles in this way regardless of where those 4 points are - even if all 4 points are the same point we can put each rectangle to the "north-west","north-east", "south-east" and "south-west" from that point. But I have no proof. And what could be solution(apart from the "try all combinations until you succeed")? So let's have 4 random points: A(Xa, Ya), B(Xb, Yb), C(Xc, Yc), D(Xd, Yd) and we need to determine for each point where would their rectangle be placed relative to the point - NW, NE, SE, SW.

Harmonic Kolobok
  • 1
  • 1
    Order the 4 points from left to right. Take the two left most points and put the first rectangle NW of the upper one and the second rectangle SW of the lower one. Proceed accordingly with the two right most points. In case of ties decide arbitrarily. – Andreas Lenz Mar 29 '23 at 22:31
  • 1
    Thank you! I've found this solution before, but then confused myself and "proved" it wrong. Now that I look at it from another perspective it looks like a correct one after all. – Harmonic Kolobok Mar 30 '23 at 11:36
  • You're welcome :) you could prove correctness by arguing that the two left rectangles cannot overlap with the two right ones, as their rightmost points are left of the leftmost points of the rectangles at the right. A similar argument shows that the two left rectangles cannot overlap with one another (and the two right triangles cannot overlap either). – Andreas Lenz Mar 30 '23 at 13:22

0 Answers0