Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
From: SourceForge.net <noreply@so...>  20051125 08:07:03

Bugs item #1365234, was opened at 20051124 14:18 Message generated for change (Comment added) made by pjrm You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=604306&aid=1365234&group_id=93438 Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None Status: Open Resolution: None >Priority: 3 Submitted By: bulia byak (buliabyak) Assigned to: Peter J. R. Moulder (pjrm) >Summary: remove overlap not locally optimal Initial Comment: This file shows one of the two configurations that you get by selecting all and removing overlaps in the file attached to the previous bug. Not to mention that the existence of two outcomes by itself suggests that one of them is nonoptimal, but in this attached file, one of the rects (it is annotated by a text label) clearly was moved farther than necessary.  >Comment By: Peter J. R. Moulder (pjrm) Date: 20051125 19:07 Message: Logged In: YES user_id=827826 It's understandable not to have the optimal solution to an NPcomplete problem, but the solution in question is not even optimal just in the x dimension (wrt the constraints from current visibility); and of course solving in one dimension wrt a fixed set of inequality (separation) constraints is not NP complete, and indeed the code already includes a solver for essentially this problem: with the only difference that we should take the mean of the goal positions (i.e. the original positions) rather than the mean of the current positions; calculation of constraints (visibility graph) is of course still to be wrt current positions. I still don't have a proof that the number of passes required is bounded by a polynomial, but the intuition is that very few passes will be needed usually: I'd expect the number of boxes that move each pass to be a small fraction of the number that moved in the previous pass. A priori, I think it reasonable for a user to expect the solution to be "locally" optimal (in the sense described above), and accordingly am tentatively leaving this open as a Bug rather than Feature Request. (I am reducing the priority to 3 though.) Re what happened in this case: Presumably what happened is that in the x pass, the rectangle in question was constrained to be to the right of what has become the bottom rectangle; then in the y pass, this bottom rectangle has been moved down such that those two no longer overlap in y, so this x constraint can now be removed and the rectangle in question allowed to move left.  Comment By: Tim Dwyer (tgdwyer) Date: 20051125 15:41 Message: Logged In: YES user_id=106477 We will further investigate the nondeterminism... that shouldn't happen! But that's already filed under a different bug report. As for optimality, this is not a bug but a limitation of the algorithm. The algorithm does not gaurantee an overall optimal solution  in fact the overall problem is NPcomplete, meaning there is no fast way of searching the (exponential) solution space to find the optimal solution. Instead, we remove overlaps in two passes, first removing some overlaps in the xdimension (moving boxes as little as possible) then resolving the remain overlaps in the ydimension. Each pass returns an optimal solution subject to the constraints in that dimension, but there is a fairly simple heuristic used to decide whether or not to resolve the overlap in the xdimension rather than the xdimension. In the example you give (it's hard to see what's going on) but I assume the labelled block is shifted to eliminate overlap in the xdimension  the shift later being made redundant by movement in the ydimension. It's possible to dream up more complicated heuristics that may give a better overall solution or possibly to run the algorithm iteratively until no more improvement is possible... we will experiment with these things further in the future. If you're interested more details on the algorithm are available here: http://www.csse.monash.edu.au/~tdwyer/FastNodeOverlapRemoval.pdf  You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=604306&aid=1365234&group_id=93438 
From: SourceForge.net <noreply@so...>  20051216 06:21:59

Bugs item #1365234, was opened at 20051124 14:18 Message generated for change (Comment added) made by tgdwyer You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=604306&aid=1365234&group_id=93438 Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None Status: Open Resolution: None Priority: 3 Submitted By: bulia byak (buliabyak) Assigned to: Peter J. R. Moulder (pjrm) Summary: remove overlap not locally optimal Initial Comment: This file shows one of the two configurations that you get by selecting all and removing overlaps in the file attached to the previous bug. Not to mention that the existence of two outcomes by itself suggests that one of them is nonoptimal, but in this attached file, one of the rects (it is annotated by a text label) clearly was moved farther than necessary.  >Comment By: Tim Dwyer (tgdwyer) Date: 20051216 17:21 Message: Logged In: YES user_id=106477 There's been some refinement and bug fixes to the algorithm since this report was filed. I've attached the result of running the current version of the overlap removal against Bulia's example. I think it looks a lot better ;), can we remove this as a bug now? Can someone find an example that is still obviously extremely nonoptimal? I am also  Comment By: Peter J. R. Moulder (pjrm) Date: 20051125 19:07 Message: Logged In: YES user_id=827826 It's understandable not to have the optimal solution to an NPcomplete problem, but the solution in question is not even optimal just in the x dimension (wrt the constraints from current visibility); and of course solving in one dimension wrt a fixed set of inequality (separation) constraints is not NP complete, and indeed the code already includes a solver for essentially this problem: with the only difference that we should take the mean of the goal positions (i.e. the original positions) rather than the mean of the current positions; calculation of constraints (visibility graph) is of course still to be wrt current positions. I still don't have a proof that the number of passes required is bounded by a polynomial, but the intuition is that very few passes will be needed usually: I'd expect the number of boxes that move each pass to be a small fraction of the number that moved in the previous pass. A priori, I think it reasonable for a user to expect the solution to be "locally" optimal (in the sense described above), and accordingly am tentatively leaving this open as a Bug rather than Feature Request. (I am reducing the priority to 3 though.) Re what happened in this case: Presumably what happened is that in the x pass, the rectangle in question was constrained to be to the right of what has become the bottom rectangle; then in the y pass, this bottom rectangle has been moved down such that those two no longer overlap in y, so this x constraint can now be removed and the rectangle in question allowed to move left.  Comment By: Tim Dwyer (tgdwyer) Date: 20051125 15:41 Message: Logged In: YES user_id=106477 We will further investigate the nondeterminism... that shouldn't happen! But that's already filed under a different bug report. As for optimality, this is not a bug but a limitation of the algorithm. The algorithm does not gaurantee an overall optimal solution  in fact the overall problem is NPcomplete, meaning there is no fast way of searching the (exponential) solution space to find the optimal solution. Instead, we remove overlaps in two passes, first removing some overlaps in the xdimension (moving boxes as little as possible) then resolving the remain overlaps in the ydimension. Each pass returns an optimal solution subject to the constraints in that dimension, but there is a fairly simple heuristic used to decide whether or not to resolve the overlap in the xdimension rather than the xdimension. In the example you give (it's hard to see what's going on) but I assume the labelled block is shifted to eliminate overlap in the xdimension  the shift later being made redundant by movement in the ydimension. It's possible to dream up more complicated heuristics that may give a better overall solution or possibly to run the algorithm iteratively until no more improvement is possible... we will experiment with these things further in the future. If you're interested more details on the algorithm are available here: http://www.csse.monash.edu.au/~tdwyer/FastNodeOverlapRemoval.pdf  You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=604306&aid=1365234&group_id=93438 
From: SourceForge.net <noreply@so...>  20051216 07:32:13

Bugs item #1365234, was opened at 20051124 14:18 Message generated for change (Comment added) made by tgdwyer You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=604306&aid=1365234&group_id=93438 Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None Status: Open Resolution: None Priority: 3 Submitted By: bulia byak (buliabyak) Assigned to: Peter J. R. Moulder (pjrm) Summary: remove overlap not locally optimal Initial Comment: This file shows one of the two configurations that you get by selecting all and removing overlaps in the file attached to the previous bug. Not to mention that the existence of two outcomes by itself suggests that one of them is nonoptimal, but in this attached file, one of the rects (it is annotated by a text label) clearly was moved farther than necessary.  >Comment By: Tim Dwyer (tgdwyer) Date: 20051216 18:32 Message: Logged In: YES user_id=106477 Whoops, didn't finish that last thought. Anyway, it is still relatively easy to generate an example where after a horizontal and vertical pass a few things could easily be moved closer to their original positions. Eventually we'll get an incremental version that will allow the algorithm to be run iteratively as Peter suggests. The tradeoff will be running time. Maybe the user can specify a maximum number of passes. In the meantime, I don't think this needs to remain as a bug, certainly I think the nondeterminism is fixed?  Comment By: Tim Dwyer (tgdwyer) Date: 20051216 17:21 Message: Logged In: YES user_id=106477 There's been some refinement and bug fixes to the algorithm since this report was filed. I've attached the result of running the current version of the overlap removal against Bulia's example. I think it looks a lot better ;), can we remove this as a bug now? Can someone find an example that is still obviously extremely nonoptimal? I am also  Comment By: Peter J. R. Moulder (pjrm) Date: 20051125 19:07 Message: Logged In: YES user_id=827826 It's understandable not to have the optimal solution to an NPcomplete problem, but the solution in question is not even optimal just in the x dimension (wrt the constraints from current visibility); and of course solving in one dimension wrt a fixed set of inequality (separation) constraints is not NP complete, and indeed the code already includes a solver for essentially this problem: with the only difference that we should take the mean of the goal positions (i.e. the original positions) rather than the mean of the current positions; calculation of constraints (visibility graph) is of course still to be wrt current positions. I still don't have a proof that the number of passes required is bounded by a polynomial, but the intuition is that very few passes will be needed usually: I'd expect the number of boxes that move each pass to be a small fraction of the number that moved in the previous pass. A priori, I think it reasonable for a user to expect the solution to be "locally" optimal (in the sense described above), and accordingly am tentatively leaving this open as a Bug rather than Feature Request. (I am reducing the priority to 3 though.) Re what happened in this case: Presumably what happened is that in the x pass, the rectangle in question was constrained to be to the right of what has become the bottom rectangle; then in the y pass, this bottom rectangle has been moved down such that those two no longer overlap in y, so this x constraint can now be removed and the rectangle in question allowed to move left.  Comment By: Tim Dwyer (tgdwyer) Date: 20051125 15:41 Message: Logged In: YES user_id=106477 We will further investigate the nondeterminism... that shouldn't happen! But that's already filed under a different bug report. As for optimality, this is not a bug but a limitation of the algorithm. The algorithm does not gaurantee an overall optimal solution  in fact the overall problem is NPcomplete, meaning there is no fast way of searching the (exponential) solution space to find the optimal solution. Instead, we remove overlaps in two passes, first removing some overlaps in the xdimension (moving boxes as little as possible) then resolving the remain overlaps in the ydimension. Each pass returns an optimal solution subject to the constraints in that dimension, but there is a fairly simple heuristic used to decide whether or not to resolve the overlap in the xdimension rather than the xdimension. In the example you give (it's hard to see what's going on) but I assume the labelled block is shifted to eliminate overlap in the xdimension  the shift later being made redundant by movement in the ydimension. It's possible to dream up more complicated heuristics that may give a better overall solution or possibly to run the algorithm iteratively until no more improvement is possible... we will experiment with these things further in the future. If you're interested more details on the algorithm are available here: http://www.csse.monash.edu.au/~tdwyer/FastNodeOverlapRemoval.pdf  You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=604306&aid=1365234&group_id=93438 
From: SourceForge.net <noreply@so...>  20051216 08:27:15

Bugs item #1365234, was opened at 20051124 06:18 Message generated for change (Comment added) made by buliabyak You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=604306&aid=1365234&group_id=93438 Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None >Status: Closed >Resolution: Fixed Priority: 3 Submitted By: bulia byak (buliabyak) Assigned to: Peter J. R. Moulder (pjrm) Summary: remove overlap not locally optimal Initial Comment: This file shows one of the two configurations that you get by selecting all and removing overlaps in the file attached to the previous bug. Not to mention that the existence of two outcomes by itself suggests that one of them is nonoptimal, but in this attached file, one of the rects (it is annotated by a text label) clearly was moved farther than necessary.  >Comment By: bulia byak (buliabyak) Date: 20051216 11:27 Message: Logged In: YES user_id=741217 Fixed, thanks, closing  Comment By: Tim Dwyer (tgdwyer) Date: 20051216 10:32 Message: Logged In: YES user_id=106477 Whoops, didn't finish that last thought. Anyway, it is still relatively easy to generate an example where after a horizontal and vertical pass a few things could easily be moved closer to their original positions. Eventually we'll get an incremental version that will allow the algorithm to be run iteratively as Peter suggests. The tradeoff will be running time. Maybe the user can specify a maximum number of passes. In the meantime, I don't think this needs to remain as a bug, certainly I think the nondeterminism is fixed?  Comment By: Tim Dwyer (tgdwyer) Date: 20051216 09:21 Message: Logged In: YES user_id=106477 There's been some refinement and bug fixes to the algorithm since this report was filed. I've attached the result of running the current version of the overlap removal against Bulia's example. I think it looks a lot better ;), can we remove this as a bug now? Can someone find an example that is still obviously extremely nonoptimal? I am also  Comment By: Peter J. R. Moulder (pjrm) Date: 20051125 11:07 Message: Logged In: YES user_id=827826 It's understandable not to have the optimal solution to an NPcomplete problem, but the solution in question is not even optimal just in the x dimension (wrt the constraints from current visibility); and of course solving in one dimension wrt a fixed set of inequality (separation) constraints is not NP complete, and indeed the code already includes a solver for essentially this problem: with the only difference that we should take the mean of the goal positions (i.e. the original positions) rather than the mean of the current positions; calculation of constraints (visibility graph) is of course still to be wrt current positions. I still don't have a proof that the number of passes required is bounded by a polynomial, but the intuition is that very few passes will be needed usually: I'd expect the number of boxes that move each pass to be a small fraction of the number that moved in the previous pass. A priori, I think it reasonable for a user to expect the solution to be "locally" optimal (in the sense described above), and accordingly am tentatively leaving this open as a Bug rather than Feature Request. (I am reducing the priority to 3 though.) Re what happened in this case: Presumably what happened is that in the x pass, the rectangle in question was constrained to be to the right of what has become the bottom rectangle; then in the y pass, this bottom rectangle has been moved down such that those two no longer overlap in y, so this x constraint can now be removed and the rectangle in question allowed to move left.  Comment By: Tim Dwyer (tgdwyer) Date: 20051125 07:41 Message: Logged In: YES user_id=106477 We will further investigate the nondeterminism... that shouldn't happen! But that's already filed under a different bug report. As for optimality, this is not a bug but a limitation of the algorithm. The algorithm does not gaurantee an overall optimal solution  in fact the overall problem is NPcomplete, meaning there is no fast way of searching the (exponential) solution space to find the optimal solution. Instead, we remove overlaps in two passes, first removing some overlaps in the xdimension (moving boxes as little as possible) then resolving the remain overlaps in the ydimension. Each pass returns an optimal solution subject to the constraints in that dimension, but there is a fairly simple heuristic used to decide whether or not to resolve the overlap in the xdimension rather than the xdimension. In the example you give (it's hard to see what's going on) but I assume the labelled block is shifted to eliminate overlap in the xdimension  the shift later being made redundant by movement in the ydimension. It's possible to dream up more complicated heuristics that may give a better overall solution or possibly to run the algorithm iteratively until no more improvement is possible... we will experiment with these things further in the future. If you're interested more details on the algorithm are available here: http://www.csse.monash.edu.au/~tdwyer/FastNodeOverlapRemoval.pdf  You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=604306&aid=1365234&group_id=93438 
Sign up for the SourceForge newsletter:
No, thanks