Results 1 to 2 of 2
  1. #1
    xtrmi is offline Member
    Join Date
    Jan 2009
    Rep Power

    Default Interesting CS problem. Need help.

    I am working on implementing the plane sweep algorithm to solve the closest points problem and it works, but about 10/1000 times I get the wrong answer. The instructions I'm following say to have an array of x coordinates sorted and use a TreeSet to sort the points inside the strip by their y coordinates. I'm getting errors when I try to add two points to the BST and they have the same Y coordinate. I've been hitting my head on the wall for a while now. Does anybody have any suggestions or hints?

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    New Zealand
    Rep Power


    Perhaps you could post some brief code to illustrate the problem?

    When I first used TreeSet I was bitten by the requirement stated in the API documentation that "the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface."

    Suppose I had a TreeSet made from a comparator that just compared two points' y-coords and return zero if the y-coords were equal. What would happen when I added two distimct points with the same y-coord to the set?

    Java Code:
    import java.awt.Point;
    import java.util.Comparator;
    import java.util.SortedSet;
    import java.util.TreeSet;
    public class TreeSetEg {
        static Comparator<Point> yCoordComp = new Comparator<Point>() {
            public int compare(Point o1, Point o2) {
                return o1.y - o2.y;
        public static void main(String[] args) {
            SortedSet<Point> set = new TreeSet<Point>(yCoordComp);
            set.add(new Point(0, 42));
            set.add(new Point(666, 42));
            System.out.println("size=" + set.size());
    This may or may not be your problem. Hard to say without knowing what your problem is.

Similar Threads

  1. [SOLVED] Interesting question about Semaphore
    By l_m_b in forum Threads and Synchronization
    Replies: 4
    Last Post: 02-13-2009, 06:35 AM
  2. Interesting Experiment
    By uncommon in forum Advanced Java
    Replies: 13
    Last Post: 12-20-2008, 11:30 PM
  3. Interesting topic in JComboBox
    By success21061985 in forum NetBeans
    Replies: 0
    Last Post: 08-21-2008, 12:43 PM
  4. Tricky but very interesting problem
    By ravjot28 in forum New To Java
    Replies: 4
    Last Post: 06-26-2008, 01:43 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts