Creating Disjoint Sets

This is a discussion on Creating Disjoint Sets within the Tech Board forums, part of the Community Boards category; I'm sure someone else in the world has thought a great deal about this, but my Google-foo is thwarted by ...

  1. #1
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399

    Creating Disjoint Sets

    I'm sure someone else in the world has thought a great deal about this, but my Google-foo is thwarted by not knowing what keywords to use.

    One way to think about the problem: I have some number of hyperrectangles. These shapes may overlap. I want to slice up my hyperrectangles into smaller hyperrectangles such that:
    1. No hyperrectangles overlap.
    2. There are as few hyperrectangles as possible.
    Here is a visual example in two dimensions.

    I'm trying to come up with a good algorithmic way of doing this without using a ton of memory. Any suggestions for search terms or algorithms would be appreciated.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  2. #2
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    If you extend either the vertical line segments of the inner rectangle or the horizontal lines of the inner rectangle you will always have the right number of splits. The only chore here is to determine which rectangle's edges to extend. In your 2D example the decision is trivial. Most of the algorithm would be to find which rectangle edges to extend to create more rectangles.

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,510
    I was thinking along those lines.

    Getting the right edges couldn't be a "simple" matter of looking for those edges inside each rectangle? You can easily check this by simply checking if any of the corners of rectangle A are located inside Rectangle B area. You'll then extend those corners in the x and y and z axis.

    The only problem I see is if you allow for each rectangle to be rotated differently. I wouldn't know how to slice the rectangles if that happened. Not in 2D or 3D. You wouldn't come up with rectangles or hyperrectangles. I'm not sure how it could be handled with the Cartesian coordinates in 3D also. But maybe the polar coordinates helped?
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  4. #4
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    I'm not sure how you would find all the smaller rectangles if we are talking about two rectangles that have arbitrary rotations. That would be quite complex. However if the rectangles are always axis-aligned then the algorithm is much simpler as Mario has suggested.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem aligning floating point numbers
    By esbo in forum C Programming
    Replies: 4
    Last Post: 01-05-2009, 07:09 PM
  2. Profiler Valgrind
    By afflictedd2 in forum C++ Programming
    Replies: 4
    Last Post: 07-18-2008, 09:38 AM
  3. disjoint sets conceptual question
    By axon in forum C++ Programming
    Replies: 1
    Last Post: 03-01-2004, 09:49 PM
  4. creating new sets
    By axon in forum C++ Programming
    Replies: 7
    Last Post: 12-03-2003, 05:37 PM
  5. Disjoint Sets
    By roberto81 in forum C++ Programming
    Replies: 19
    Last Post: 11-30-2002, 09:03 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21