5
$\begingroup$

I have encountered the following problem.

We have $N$ points in discrete coordinates,distributed through a plane with vertical axis $[1..Y]$ and horizontal axis $[1..X]$. We can perform the action of removing all points with vertical coordinate $y$, in short removing $y$.

example

What is the least number of $y$'$s$ we must remove so that the number of $x$ that have points is less than $X/2$. For example in the graph above removing 1 and 2 leaves points only in 1,3,6,9.

This seems like a NP-complete problem to me so the only solution I have developed is removing all combinations of $y'$s. I would be grateful if someone experienced in computation-theory could point me to a similar known problem (or maybe a problem this could be reduced to), any suggestion is welcome.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ You're not clear. What's point with vertical coordinate y? All points have both x and y coords. What is "how many y"? $\endgroup$ – SomeWittyUsername Nov 7 '12 at 18:51
  • 1
    $\begingroup$ "How many y must we remove so that the number of x that have points is less than X/2". Do you mean "at least how many y" or "at most how many y"? $\endgroup$ – aam1r Nov 7 '12 at 19:39
  • 1
    $\begingroup$ Whenever you say NP you mean NP-complete, right? $\endgroup$ – A.Schulz Nov 7 '12 at 20:44
  • $\begingroup$ Can't you simply do this greedily? It never makes sense to not remove a row with the largest number of entries, right? $\endgroup$ – Pål GD Nov 7 '12 at 21:38
  • $\begingroup$ Yes, i mean NP-complete. Thank you for the corrections. $\endgroup$ – manix Nov 7 '12 at 21:52
3
$\begingroup$

If you mean by "the number of $x$ that have points" that the number of distinct values $x$ such that there is a point $(x, y)$ such that $y$ has not been removed is at most $X/2$, then your problem is extremely similar to Set Cover, which is $\mathbf{NP}$-complete.

Your problem would be the variant in which you ask for the minimum number of sets needed to cover half the elements of your universe. I would be very surprised if this was not $\mathbf{NP}$-complete. I'll think about it some more and update this if I think up a proof of $\mathbf{NP}$-completeness.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Your answer is what I was expecting. Indeed, at first sight, Set Cover seems the same as my problem. $\endgroup$ – manix Nov 7 '12 at 22:16
  • $\begingroup$ @manix: actually, my answer is nonsense. The obvious reduction from Set Cover would work if an x-coordinate is 'satisfied' (=removed) if any point on that line is removed rather than all points, as in your problem. If you unaccept it, I will delete it and try to come up with a true answer :) $\endgroup$ – Alex ten Brink Nov 7 '12 at 23:48
  • $\begingroup$ It is the opposite of the variant of Set Cover you proposed. The minimum number of sets so that half the elements are uncovered. Maybe you can edit this post, the discussion is very helpful to me. $\endgroup$ – manix Nov 8 '12 at 1:09
  • $\begingroup$ It occurred to me that another candidate for reduction might be the Maximum Coverage problem. My problem can be expressed as the maximum number of sets such that only half the elements are covered. $\endgroup$ – manix Nov 8 '12 at 22:24
2
$\begingroup$

I can think of a O(n log n) solution:

  • Input: the set of all 2-D points on your graph in the form of (a, b) - where a is the x-coordinate and b is the y-coordinate. Assumption: points are unique. O(n)
  • Build a HashTable to count the occurrences of each distinct y-coordinate, b, over this set. (i.e. b is the key and its occurrence is the value) For example: 5 total points with b==3, 4 total points with b==7, etc. O(n)
  • Sort the HashTable in descending order on b, based on its occurrence count: largest occurrence count first. O(n log n)
  • While number of x that have points is still more than X/2, loop: O(n)
    • Remove the top entry in the sorted result from the HashTable O(1)
    • (number of x remaining) = (number of x remaining) - corresponding occurrence count with this entry. O(1)
    • Increment a count of how many entries removed so far O(1)
  • Output the count of how many entries removed, and that is the minimum number of y's that you have to remove to get number of x's that have points less than X/2

Total complexity:

  • Runtime: O(n log n)
  • Space: O(n) (to store input and to build the HashTable)

Here's a walkthrough of the algorithm with the example provided by your image:

We have as input the points:

(1, 1)
(1, 4)
(2, 2)
(3, 3)
(3, 4)
(4, 2)
(5, 2)
(6, 3)
(7, 1)
(8, 1)
(9, 3)

Putting the y-coordinates b into a HashTable with b as the key and its occurrence as the value:

{
    "1": 3,
    "2": 3,
    "3": 3,
    "4": 2,
}

This is a sorted order based on the occurrence count, so we first remove y at 1, this removes the points:

(1, 1)
(7, 1)
(8, 1)

and then move y at 2:

(2, 2)
(4, 2)
(5, 2)

and we are done.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is a greedy algorithm that does not guarantee the minimal solution, but it gives an upper bound. It works in the example because most of the colons have only one point. $\endgroup$ – manix Nov 7 '12 at 22:01
  • $\begingroup$ @manix I realized afterwards that I misunderstood the question - perhaps instead of removing the y's that have the most points, find the x's with the least points and remove the corresponding y's? $\endgroup$ – sampson-chen Nov 7 '12 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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