Finding lower bound for nlogn algorithm

Question

The initial problem was discussed here: Algorithm for finding a special point k in O (n log n) time

We just have an algorithm that determines whether a set of points in a plane has a center of symmetry or not.

I wonder if there is a way to prove a lower bound (nlogn) to this algorithm? I think we need to use this algorithm to solve a simpler problem, such as sorting, element uniqueness or set uniqueness, so we can conclude that if we can solve, for example, element uniqueness using this algorithm, it can be at least nlogn .

It seems that the solution has something to do with the uniqueness of the element, but I could not find a way to manipulate this into the symmetry symmetry algorithm.

Answer 1

Mark this article

The idea is that we can reduce Problem A to Problem B, then B is no more complicated than A.

However, if task B has a lower bound Ω (nlogn), then task A is guaranteed by the same lower bound.

In the article, the author chose the following relatively affordable problem: B: given two sets of n real numbers, we want to decide whether they are identical or not.

Obviously, this introduced problem has a lower bound Ω (nlogn). Here, as the author reduced our problem to the introduced problem (A, B denote two real sets in the following context):

Answer 2

First notice that your magic point k should be in the center.

• build a search data structure indexed by vector position (O (nlog n))
• calculate the center of gravity of the set of points (O (n))
• for each point, calculate the vector position of its opposite and check its existence in the search structure (O (log n) * n)

Appropriate search data structures can include everything that allows you to efficiently search for content, including balanced trees, window trees, hash tables, etc.