This seems to work pretty well on any dataset produced by your generator, along with a few variations on that, that I've tried:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];
use GD::Graph::lines;
use GD::Graph::colour qw(:colours :lists :files :convert);

my $graph = GD::Graph::lines->new( 6000, 768 );

die 'No data file specified' unless @ARGV and -e $ARGV[ 0 ];
open my $fh, '<', $ARGV[ 0 ] or die "Couldn't open $ARGV[ 0 ]";

my @data = ([],[]);
push( @{ $data[ 0 ] }, $1 ), push( @{ $data[ 1 ] },  $2 )
    while <$fh> =~ m[(\S+)\s+(\S+)];

close $fh;
#pp \@data; <>;


$graph->set(
    title             => 'Y over X',
    'bgclr' => 'white',
    'transparent' => 0,

    x_label           => 'X',
    x_max_value       => 6000,
    x_tick_number     => 6,

    y_label           => 'Y',
    y_tick_number     => 8,

) or die $graph->error;

my @hilos;
my $crossover = $data[1][0];
my $dir = $data[1][1] > $crossover;
my( $max, $min ) = ( -1e308, 1e308 );
my $count = 0;

for my $y ( @{ $data[ 1 ] } ) {
    ++$count;
    $max = $y if $y > $max;
    $min = $y if $y < $min;
    if( $dir and $y < $crossover ) {
        push @hilos, ( $max ) x $count;
        $count = 0;
        $dir = 0;
        $max = $crossover;
    }
    elsif( !$dir and $y > $crossover ) {
        push @hilos, ( $min ) x $count;
        $count = 0;
        $dir = 1;
        $min = $crossover;
    }
}

push @data, \@hilos;

my $gd = $graph->plot( \@data ) or die $graph->error;

open(IMG, '>800691.png') or die $!;
binmode IMG;
print IMG $gd->png;
close IMG;

system '800691.png';
[download]

It should be reasonably efficient as there's no sorting involved, just a single pass through the data. Just supply the script with the name of the data file as its only argument. The maximas and minimas (do they have a collective name? extremas?), will be plotted as a square wave in green overlaying the data in red.

It's easy to see datasets that it would screw up on, but it just depends how good a model your generator is?