Packing 'x' out of 'n' dots into the smallest square possible

[BiFii]

Imagine a two dimensional area with a random arangement of dots. The coordinates of every dot are saved in one array.

 

n: Amount of dots in the area.

 

The task is to find the smallest square which catches at least a given amount of dots.

 

x: Amount of dots that should be contained by the square.

 

So... I need to find the smallest square which contains at least x out of n dots.

 

I basically search for an efficient algorithm to do this.

 

 

Feel free to ask as much questions as you want.

 

I'm programming in java.

[loganryan99]

The first method that comes to mind is picking a point inside of the area and creating a square, then slowly expanding the square until it contains the amount of dots you want it to. This would require brute force to be accurate 100% of the time (cycle though every possible point) although I'm sure you could find the densest area of dots and start there.

 

I'm tired right now so my explanation might not be the best, so if this makes no sense tell me and I'll try to explain it better

[Ciccioo]

i thought of a possible recursive implementation that goes like this:

i'll assume that your area is squared for ease, if that assumption is incorrect this needs some more work

 

so let's say that the area is L * L

you start off considering the biggest square possible of size L*L that is as big as the whole area

then you shrink the square in all the 4 possible ways, and you recursively test those 4 squares

by 'testing a square' i mean that you just count the dots in it: if it contains at least x dots, then you can shrink it further to search a better packaging. if it contains less than x dots, that path shall be abandoned

 

i hope that was not a confusing explaination

 

edit:

alternatively, you can start with the smallest square of size sqrt(x) and make it slide all over the area to search for a zone where it will contain x dots. if you don't find that zone, make the square a unit bigger and start over

the first method looks much better to me, especially if the area is large and the dots have a low-density distribution

[BiFii]

Ok. so I thought about the first method already. But what if the desired smallest square is crossing the boundaries of for example two quarters of the whole square.

The second method is not an Option I think. The coordinates are in the range of Type "long". I cant just Test every Single square if it fits.

Gesendet von meinem HTC One mit Tapatalk

[Ciccioo]

Ok. so I thought about the first method already. But what if the desired smallest square is crossing the boundaries of for example two quarters of the whole square.

The second method is not an Option I think. The coordinates are in the range of Type "long". I cant just Test every Single square if it fits.

Gesendet von meinem HTC One mit Tapatalk

mmm i don't see the problem

 

the 4 subsquares i'm talking about are these:

subsquare 1:

2:

3:

4:

 

anyway i found this interesting so i implemented it, and here's what i found out: the computation time highly depends on how the input is done, but these ase some results:

20 dots out of 100 in a 20x20 area: 500ms

20 dots out of 100 in a 22x22 area: 2s

20 dots out of 100 in a 25x25 area: 45s

80 dots out of 100 in a 100x100 area: 46s

...and then it goes crazy

 

now, my program is actually pretty stupid and could be much improved, but i don't think that computing an area 'in the range of type long' is doable, that's a lot of squares

hopefully i'm wrong though, let's see if someone can come up with a better idea

 

an improvement that could be done to the first method is to build a second area that is kind of a shrunk down version of the first: every cell in this new area would count the total amount of dots in the respective zone of the first area. that would speed up things if the dots are really a lot

original square:OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

OOOOOOXOOOOOOXOOOOOOXOOOOOOXOOOOOOXOOOOOOXXXXXXXX

XOOOOOOXOOOOOOXOOOOOOXOOOOOOXOOOOOOXOOOOOOXXXXXXX

XXXXXXXOOOOOOXOOOOOOXOOOOOOXOOOOOOXOOOOOOXOOOOOOX

XXXXXXXXOOOOOOXOOOOOOXOOOOOOXOOOOOOXOOOOOOXOOOOOO

[BiFii]

Mm Yes. Recursive implementation is probably Not very intelligent with numbers this big.

I think I need to aim for a runtime of about n^2 iterations.

So what if I build a square at each dot, which expands only to the right until x amount of dots are caught in it.

The Output should be the side length of the square and the coordinates of every dot in the square.

Gesendet von meinem HTC One mit Tapatalk

[Ciccioo]

So what if I build a square at each dot, which expands only to the right until x amount of dots are caught in it.

that wouldn't find the solution to this with N = 3, X = 3, you would need the square to expand in every direction to find certain solutions

XOXOXXXXOX = emptyO = dot

and it would make a lot of attempts anyway

hm i dunno

 

anyway, a number of elements in the range of long? that's gigabytes and gigabytes of memory if you want to map it all on a 2d array

 

edit: the algorithm i thought about that explores squares like this

original square:

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

subsquare 1:

OOOOOOX

OOOOOOX

OOOOOOX

OOOOOOX

OOOOOOX

OOOOOOX

XXXXXXX

2:

XOOOOOO

XOOOOOO

XOOOOOO

XOOOOOO

XOOOOOO

XOOOOOO

XXXXXXX

3:

XXXXXXX

OOOOOOX

OOOOOOX

OOOOOOX

OOOOOOX

OOOOOOX

OOOOOOX

4:

XXXXXXX

XOOOOOO

XOOOOOO

XOOOOOO

XOOOOOO

XOOOOOO

XOOOOOO

is actually performing very very poorly because if you explore nodes this way, every square is visited more than once (actually it could be visited thousands, millions of times)

i can't think of a way to fix it right now, but i'll think about it

[fizzlesticks]

Brute force is the only way I can think of.

 

First loop through the points keeping track of the minimum x, minimum y, max x and max y.

Then use nested loops going from min x to max x and min y to max y.

Treat each point as the center of the square and keep expanding until it contains the needed number of points or is bigger than the smallest square you've found.

 

Though like Ciccioo said, longs have a huge range. If you really need to search that entire area it's going to take forever.

[BiFii]

Just got a "Tip" ...

Form a square around every combination of x out of n dots.

I can definetly optimize this algorithm to not test every combination But only those which makes Sense at the Time of testing.

This would result in n over x possibilities, which is a large number But like I said.. definetly optimizable

Gesendet von meinem HTC One mit Tapatalk

[wolfsinner]

I don't know your problem solving background but, at first glance, this seems like an ad-hoc problem. This means that there isn't a well-known algorithm that can be applied directly this problem.

 

Without thinking much, I can see this being solved with dynamic programming. Breadth-first search, allied with some hashed structure for memoization. Make the smallest possible rectangle that contains all dots, then search for smaller squares.

[BiFii]

Holy mother of words I dont know.. I'm a second semester computer science Student fyi

Gesendet von meinem HTC One mit Tapatalk

[Ciccioo]

Holy mother of words I dont know.. I'm a second semester computer science Student fyi

Gesendet von meinem HTC One mit Tapatalk

maybe there is some extra information in the assignment text that can make the problem easier? some additional clausole? peculiarity of the input?

[BiFii]

If I get Home I'm gonna try to translate everything important.

Its even harder for me to understand you guys as a non native english speaker.

I wish America would have stayed in Germany after World War II :DDD

Gesendet von meinem HTC One mit Tapatalk

[wolfsinner]

Holy mother of words I dont know.. I'm a second semester computer science Student fyi

Gesendet von meinem HTC One mit Tapatalk

 

I see. Well, since you were talking time complexity, I thought maybe you'd know graph theory search.

 

Is this an assignment for University? If so, what course is it? Is there an upper limit for the total number of dots?

There are simple solutions to this problem, but none are O(n²) as far as I can tell, especially without graph theory.

If you DO know graph theory, but simply no search algorithms on graphs, a simple approach is the following (assuming the upper limit for number of dots isn't unbelievably large):

1. Generate a complete graph on the dots, and store each vertex edge in crescent order by distance (you can only store the smallest x edges).
2. For each vertex, get the first x edges and calculate the size of the bounding square, and check if it's min.

Done right and without memoization, this can be O(n²log(n)), which isn't that great but close to your target complexity. I'm sorry if I'm being confusing, or if you don't know graph theory.

But considering you're in semester 2, I had already studied graph theory by then at my University, so there's good chance you have too.

[BiFii]

Great! We have just started graph theory yesterday and I think I almost know what you mean.

So you mean, I should create an edge from each dot to another, find the "lightest" edges (shortest distant) from each vertex and form a square around them?

 

If I got this right, I already had a similar idea, which lead me to a big problem:

 

The nearest x dots relative to one specific dot DO NOT have to form the smallest square.

 

The dots are named after the distance to the red dot (0). As you can see 0, 1 and 3 are forming the smallest square but not 0, 1 and 2 as you probably would think.

 

 

After that I will try to translate the assignment.

 

Translated:

 

A telescope is angled at the sky full of stars, which is given as randomly generated two dimensional positive coordinates of type long. Because it is using a special lense it is only possible to observe a squared sector which cannot be rotated. The square is always parallel to the x- and y-axis. Find for a given amount of stars n the position of the square, with which you can observe a given amount of stars k, so that the square is as small as possible.

Your program will be called with the following command line arguments:

n: amount of generated stars

k: least amount of stars caught in the square

seed: seed pretty self explanatory

Create the stars with the following method, which fills a n times 2 array with random long-numbers. One line in this array contains the x- and y-coordinate of the star:

 

static long[][] makeStars(int n, int seed) { long[][] a = new long[n][2];
    Random rand = new Random(); rand.setSeed(seed);

    for (int i = 0; i < n; i++) {
        a[0] = Math.abs(rand.nextLong()) % 100000000000000L;

        a[1] = Math.abs(rand.nextLong()) % 100000000000000L;

    }

    return a;

} 

 

Original:

 

Starseeker.java: Ein Teleskop ist auf den Sternenhimmel ausgerichtet, welcher der Ein- fachheit halber durch zufällig generierte positive 2D Koordinaten mit dem Datentyp long ge- geben ist. Durch einen entsprechenden Aufsatz ist es nur möglich, einen quadratischen Aus- schnitt zu betrachten, welcher nicht gedreht werden kann. Das Quadrat welches die gerade betrachteten Sterne umschließt ist also immer parallel zur x- bzw y-Achse des Koordinaten- systems.

Finden Sie zu einer gegebenen Anzahl an Sternen n die Position des Quadrats, mit welcher mindestens eine vorgegebene Menge k an Sternen betrachtet werden kann, so dass dieses Qua- drat kleinstmöglich ist. Ihr Programm wird dabei mit folgenden Kommandozeilenparametern aufgerufen:

n Anzahl der zu generierenden Sterne

k Anzahl der Sterne die mindestens im Quadrat liegen sollen

seed Ein Startwert mit dem die Pseudozufallszahlen generiert werden. Ein gleicher Wert für seed erzeugt also gleiche Zufallszahlen.

Erstellen Sie die Sterne mit folgender Methode, welche ein n × 2-Array vom Typ long mit Zufallszahlen füllt. Eine Zeile in diesem Array enthält also die x- und y-Koordinate eines Sterns: 

Edited June 17, 2014 by BiFii

[wolfsinner]

The algorithm will not find the optimal square for every vertex, but it will find the optimal solution.

What will happen when you work on the vertex that is connected to the red dot by edge 1 (or even 3)? Don't forget this is a complete graph, which square would it choose? 

[BiFii]

Edited!

 

The algorithm will not find the optimal square for every vertex, but it will find the optimal solution.

What will happen when you work on the vertex that is connected to the red dot by edge 1 (or even 3)? Don't forget this is a complete graph, which square would it choose? 

 

Ok so I am still very sceptic about this solution and I can't proof neither disprove it.

I guess I will try to implement it with small numbers to see if it works or not.

Your point seems logic.

 

Thank you very much for your help so far, I will keep this thread updated as I progress through the problem

[wolfsinner]

Edited!

 

 

Ok so I am still very sceptic about this solution and I can't proof neither disprove it.

I guess I will try to implement it with small numbers to see if it works or not.

Your point seems logic.

 

Thank you very much for your help so far, I will keep this thread updated as I progress through the problem

 

Well, I can't say I'm 100% confident I'm right, and don't have time to prove it theoretically, but then again that's the problem of coming up with ad-hoc solutions off the top of my head. I have an alternative solution, but it uses dynamic programming with breadth-first search. This one I know would work, but covers topics you've yet to study.

Keep us updated.

[BiFii]

Well, I can't say I'm 100% confident I'm right, and don't have time to prove it theoretically, but then again that's the problem of coming up with ad-hoc solutions off the top of my head. I have an alternative solution, but it uses dynamic programming with breadth-first search. This one I know would work, but covers topics you've yet to study.

Keep us updated.

 

Dude come at me with those "complex" methods. I know how breadth-first search works and flew over the wikipedia article about dynamic programming. That should be enough

I am happy to learn things by myself. So if you don't mind try to explain the idea

[Avratz]

Build an R-Tree and traverse it.

 

http://en.wikipedia.org/wiki/R-tree

[wolfsinner]

Dude come at me with those "complex" methods. I know how breadth-first search works and flew over the wikipedia article about dynamic programming. That should be enough

I am happy to learn things by myself. So if you don't mind try to explain the idea

 

I explained the general idea in my first post. The main difficulty of this solution is knowing when you're repeating a subproblem, and wasting memory. You would start with a large square that encompasses all of the dots, and then generate smaller squares in breadth by removing edges, testing them. Again, the difficulty would lie in finding a good structure to memoize your subproblems, which would in turn require a good hashing function. I would not recommend you take this path, especially considering it's probably not what your teacher is looking for, and that you're not experienced in these methods.

 

Don't use R-Trees. They are complex data structures which you would have to implement, and I can't even see how they'd be useful/efficient for this problem. They're mostly used to index spatial data in databases, because they're set up in a way that reduces by a huge margin the number of objects you have to search on by excluding entire groups of objects, something undesirable for this problem.

[BiFii]

Alright. So no dynamic programming and no R-trees.

 

I implemented the idea of testing every possible combination of x out of n stars.

It works.. obviously! And has a time complexity of O(n over x)... obviously! This is bananas!!! (n = 100, x = 10 is impossible)

 

Going to work on the other method which finds the nearest dots and forms a square around it.

 

It is basically this:

 

for (int i = 0; i < sky.length - (k - 1); i++) {	current[0] = i;	findMinSquare(sky, current, 1);}public static void findMinSquare(long[][] sky, int[] current, int pos) {	recCount++;	if (pos == current.length) {		analyzeCurrent(sky, current);	} else {		for (int i = 1 + current[pos - 1]; i < sky.length - (current.length - 1 - pos); i++) {			current[pos++] = i;			findMinSquare(sky, current, pos--);		}	}}

[Nuluvius]

Don't have time to sit down and really think about this in depth but perhaps this data structure might help: http://en.wikipedia.org/wiki/Quadtree

[BiFii]

Don't have time to sit down and really think about this in depth but perhaps this data structure might help: http://en.wikipedia.org/wiki/Quadtree

 

I don't think that will help me in any way. The area I have to split into multiple squares is like  100000000000000 by  100000000000000.

 

I think the solution to this problem is to limit the area in which I test all the possible combinations.

[Nuluvius]

I don't think that will help me in any way. The area I have to split into multiple squares is like  100000000000000 by  100000000000000.

 

I think the solution to this problem is to limit the area in which I test all the possible combinations.

 

Oh I wasn't directing that at you specifically. Whatever gave you that idea?