Convex Hull Problem

code-ninja has asked for the wisdom of the Perl Monks concerning the following question:

I searched the Monastery for this problem and the solution that came up used the Math::ConvexHull module.

That being said, I have problem that I'll elucidate and I know that Convex Hull algorithm will best fit the need. I coded my rendition of the Jarvis' algorithm.

Problem statement (updated): Suppose there are n events and each event is represented by a 3-tuple (x, y, z) where x is the start time, y is the end time and z is the cost of the event. for example:

Suppose that this represents all those possible events that I can attempt to earn money but clearly, I cannot attempt them all because for some events, start time overlaps with some other events, creating a deadlock. The best solution is I schedule the events in such a way that I "handpick" certain event that do not clash while not decreasing my profit (not necessarily maximize but I should not also face a loss). For example:

x y z

1 2 10
2 4 9
4 8 20
[download]

Why I think Convex Hull best fits the solution?

Well, what I did was, instead of using the 3-tuple, I calculate how much time each event will actually take (by subtracting x from y) so this way I get a set of pair of points on a Cartesian plane. Now, applying the Jarvis algorithm, I'll get one convex quadrilateral that covers all the points exactly once and returns to the original point (The Traveling Salesman Problem). This way, I'll get all those points I can schedule without getting deadlocked and my profits will be maximized.

I implemented the Jarvis algorithm from the wiki link above.

#!/usr/bin/perl

use strict;
use warnings;

my @AoA; # an array of arrays to represent the points.

while(<DATA>) {
    push @AoA, [ split ];
}

my @sorted = sort { $a->[1] <=> $b->[1] } @AoA; # thanks moritz!

=head
for my $aref ( @sorted ) {
    print "\t [ @$aref ],\n";
}
=cut

# implementing the Gift Wrap algorithm.
# the @sorted array contains all the points and that too in the sorted
+ order
# the sorting helps identify the "left most point".

my (@P, @endPoint, @pointOnHull, $i, $flag1, $flag2);
@pointOnHull = @{$sorted[0]}; # the "left most point"
$i = 0;

do {
    $P[$i] = [ @pointOnHull ];
    @endPoint = @{$sorted[0]};
    for my $j (1 .. $#sorted) {
        
        # determine position of j'th element relative to line P[i] to 
+P[endPoint]
        # it should lie to the right of the line P[i] to P[endPoint]
        # we check that if the current point's x and y co-ordinates
        # are greater than, in every respect, the current end point.
        
        if(${$sorted[$j]}[0] > $endPoint[0] && ${$sorted[$j]}[1] >= $e
+ndPoint[1]) {
            $flag1 = 1;
        }
        # check if the current end point is not a point on the hull.
        
        if($endPoint[0] != $pointOnHull[0] && $endPoint[1] != $pointOn
+Hull[1]){
            $flag2 = 1;
        }
        
        if($flag1 || $flag2) {
            @endPoint = @{$sorted[$j]};
        }
    }
    $i++;
    @pointOnHull = @endPoint;
} until ($endPoint[0] == ${$P[0]}[0] && $endPoint[1] == ${$P[0]}[1]);

# Array P is the convex hull

for my $aref ( @P ) {
    print "\t [ @$aref ],\n";
}

__DATA__
20 50
50 10
43 45
23 46
48 93
324 45
245 437
2315 4576
135 457
[download]

the code is going into an infinite loop and I'm finding it difficult to grasp why is it doing so? Any pointers? I'm unwilling to use any external module(s).

Even if convex hull algorithm does not qualify as the best solution, I'd ask respected monks to comment on the code at least. :)

PS: The problem statement may sound familiar to some. It was a problem in the ACM-ICPC 2011 final round. I'm not recalling the exact words of the problem. I was in the pre-final year of college and this was the only problem my team couldn't crack and we lost to this other team. It has been bugging me since then!

UPDATE:The exact problem statement can be found here. Thanks to hdb. problem F.

Comment on Convex Hull Problem Select or Download Code

Replies are listed 'Best First'.
Re: Convex Hull Problem by BrowserUk (Patriarch) on Aug 26, 2013 at 19:02 UTC
Problem statement: I'm given a set of points, each point being a 3-tuple (x, y, z) where x is the start time of an event, y is the end time of that event and z is the money earned if that event is scheduled/takes place. Now, it is not necessary that all events start or end at a mutually exclusive times. Events may overlap, like A(3, 4, 5) and B(3, 8, 5). Given a set of such events, I've to find a schema such that if the events are scheduled in that order, I'll get the maximum profit. Your problem description leaves me cold. If there is no constraint on events overlapping; scheduling them all will maximise profits? With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re^2: Convex Hull Problem by SuicideJunkie (Vicar) on Aug 26, 2013 at 19:46 UTC
I think that means that there are events that overlap, and are thus mutually exclusive. If none of the events overlap, then you could just choose all of them. What I don't get is: Problem statement: I'm given a set of points, each point being a 3-tuple (x, y, z) where x is the start time of an event, y is the end time of that event and z is the money earned if that event is scheduled/takes place. Now, it is not necessary that all events start or end at a mutually exclusive times. Events may overlap, like A(3, 4, 5) and B(3, 8, 5). Given a set of such events, I've to find a schema such that if the events are scheduled in that order, I'll get the maximum profit. Why would it matter what order you pick the events? Surely at the end you should just have a set of events which you have chosen and a second set which you have rejected.	[reply]
Re^3: Convex Hull Problem by BrowserUk (Patriarch) on Aug 26, 2013 at 20:03 UTC
Hm. Doesn't your "are thus mutually exclusive" conflict with his " it is not necessary* that all events start or end at a mutually exclusive times."*? With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re^4: Convex Hull Problem by SuicideJunkie (Vicar) on Aug 26, 2013 at 20:42 UTC
Re: Convex Hull Problem by code-ninja (Scribe) on Aug 27, 2013 at 03:49 UTC
The problem statement is updated. I, unfortunately, cannot find the exact problem that we faced in the ACM ICPC but I'm sure that the problem aggregated to the update.	[reply]
Re^2: Convex Hull Problem by BrowserUk (Patriarch) on Aug 27, 2013 at 08:15 UTC
The problem statement is updated. Hm. Still woolly. Does that mean you can run (service, maintain) two 'events' that overlap, provided that they do not start at the exact same time? Ie. You can 'do' b through e if you skip a? `8 9 10 11 12 1 2 3 4 5 aaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb ccccccccccccccccccc ddddddddddddddddddd eeeeeeeeeeee` [download] With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]
Re^3: Convex Hull Problem by code-ninja (Scribe) on Aug 27, 2013 at 09:59 UTC
No. Events may overlap and in such a case, I'll have to select the one with the highest cost. Keep in mind that "cost" here refers to the income I'll get for each event. Consider my example. `1 4 6 1 2 10 2 4 9 ...` [download] The first event transcends the start of the third event, right? But I'm selecting the second because it does not clash with any other and gives me maximum cost. OTOH, if the input would've been: `1 5 2 1 2 5 2 4 9 ...` [download] The first even transcends the other two but I ignore it and select `2 4 9` because the event takes less time and is more profitable. I hope its clearer now. If not, let the problem statement rest and comment on the algorithm that I coded. I'll search for the exact problem statement and repost this question. My apologies, but this question bugs me periodically and for a while I get really intense about solving it and get carried away. :).	[reply] [d/l] [select]
Re^4: Convex Hull Problem by BrowserUk (Patriarch) on Aug 27, 2013 at 10:21 UTC
Re: Convex Hull Problem by hdb (Monsignor) on Aug 27, 2013 at 11:00 UTC
Are you sure `y` is the end time? What do the following lines mean? `x y z 1 1 3 4 2 8 4 1 3` [download] It would make more sense if `y` denotes the duration.	[reply] [d/l] [select]
Re^2: Convex Hull Problem by code-ninja (Scribe) on Aug 27, 2013 at 11:11 UTC
hdb, ignore the problem statement for now. I'll search the exact problem statement and repost the question. meanwhile, help me with my code for the Convex Hull. :)	[reply]
Re^3: Convex Hull Problem by hdb (Monsignor) on Aug 27, 2013 at 11:20 UTC
Is it http://icpc.baylor.edu/download/worldfinals/problems/2011WorldFinalProblemSet.pdf, problem F?	[reply] [d/l]
Re^4: Convex Hull Problem by code-ninja (Scribe) on Aug 27, 2013 at 11:26 UTC


more useful options
	PerlMonks