chort's blog

Generalization of a geometry problem
By chort, history, 6 years ago, In English

In one of the contests I came across the following problem: Given n points (x,y) where n<=3*10^5 and |x|,|y|<=10^9.You need to find such point M(x',y') that if you look from that point on any of the given points and then rotate 180 degrees — you will also see point from the given set(on the same distance). Basically, M is the symmetry point. This task wasn't hard to solve, but because I haven't read the text carefully, at first I was trying to solve more generalized version: Find(if it exists) such point M that for every point from the set there is another point which is on the other "side"(you will see it if you rotate 180 degrees and no matter if it has another distance from M). Is there any solution for this problem? At least O(n^2)?

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In collaboration with my friend we came up with the following O(N^3logN) solution:

1) Intersect all possible segments — O(N^2): Choose any two points. Go through n-2 other points and now "create" segment from first to this point. And after fixing this segment go through other n-3 points to fix second segment.

2) Now we have two segments with some point M of their intersection(if it exists). To check if every point (from n-4 left ones) has its "mirrored" point we will use set which will store y/x of coordinates of vector formed from M to current point. For every point we do the following: If there is no such tangent in set we insert it. Otherwise we delete this tangent from set. If set is empty at the end of the cycle, then M is the answer.

*We should also consider situation when points have same tangent but they are on one "side" from M, So additionally we need to store coordinates of vector to check if new point is forming opposite vector.(by calculating dot product, for example)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can think a solution in which you store the middle points of all unordered pairs of points and then find a point in the map which which is has count of n/2 which will be a point of symmetry for the given coordinates, so for this n must be even and you can easily prove that there will be no over counting.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How are middle points connected with the answer? We don't need to find point of symmetry

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If it is guaranteed that no three points are on the same line one can calculate the solution with runtime O(n·log(n)):

Let's look at some pair of points which are "mirrored" (According to the searched point seen if one rotates by 180 degrees). The line specified by this pair of points needs to split all points in two halves of same size.

With this knowledge one can determine some "mirrored" points. For example one can take the leftmost point.

  • Sort all other points by the slope of the line form the leftmost point to the respective point.
  • The Median of all points is the mirrored point.

One can find the Median with expected time O(n) by quickselect algorithm or by sorting O(n·log(n)).

This works for all points on the convex hull. This means we need another point on the convex hull and then the solution (if there is a solution) is the cut point of the two lines specified by the two pairs of mirrored points. The check whether this is actually a solution can be done by hashing the angles to all points O(n).

So if one can find a second point on the convex hull in O(n) time then the expected complexity would be O(n). Otherwise one can simply calculate convex hull first and then do the two searches for mirrored points, which results on O(n·log(n))

→ Reply