Lower envelope of monotone polygonal chains

2014-12-20

===

Computing the lower envelope of monotone polygonal chains is important in visibility problems in robotics, facility location, video games, architecture, and so on. A simple linear search algorithm running in $O(n+mk)$ time is proposed for constructing the lower envelope of k vertices from m monotone polygonal chains in 2D with n vertices in total. This can be applied to output-sensitive construction of lower envelopes for $n$ arbitrary line segments in optimal $O(n\log k)$ time, where $k$ is the output size. Compared to existing output-sensitive algorithms for lower envelopes, this is simpler to implement, does not require complex data structures, and is a constant factor faster.

This is published in _Information Processing Letters_. [#dllu]

:: IPL paper http://dx.doi.org/10.1016/j.ipl.2015.07.004

:: arXiv version http://arxiv.org/abs/1412.6619

???
<canvas id="hi" width="1200" height="600" style="cursor:pointer; width: 100%"></canvas>
???

* [#dllu] Lu, Daniel. "Planar lower envelope of monotone polygonal chains." _Information Processing Letters_ [doi:10.1016/j.ipl.2015.07.004](http://dx.doi.org/10.1016/j.ipl.2015.07.004)

???
<script src="lol2.js"></script>
<script>
    var tt = p.length-1;
    var m = 3, k = 5;
    var w = 1200, h = 600;
    var playing = false;
    window.onload = function() {
        m = segments.length;
        k = segments[0].length;
        simpledraw();
        document.getElementById('hi').onclick = function() {
            playing = !playing;
        };
    }
    function simpledraw() {
        var ctx = document.getElementById('hi').getContext('2d');
        ctx.clearRect(0,0,w,h);
        for(var i=0; i<m; i++) {
            ctx.beginPath();
            ctx.moveTo(segments[i][0][0], h-50-segments[i][0][1]);
            for(var j=1; j<k; j++) {
                ctx.lineTo(segments[i][j][0], h-50-segments[i][j][1]);
            }
            ctx.strokeStyle = '#666'; //['#f00', '#0f0', '#00f'][i%3];
            ctx.lineWidth = 1;
            ctx.lineCap = 'round';
            ctx.lineJoin = 'round';
            ctx.stroke();
        }
        ctx.beginPath();
        ctx.moveTo(env[0][0], h-50-env[0][1]);
        for(var j=1; j<env.length; j++) {
            ctx.lineTo(env[j][0], h-50-env[j][1]);
        }
        ctx.strokeStyle = 'rgba(255,0,0,0.5)';
        ctx.lineWidth = 2;
        ctx.lineCap = 'round';
        ctx.lineJoin = 'round';
        ctx.stroke();
    }
    function draw() {
        simpledraw();
        var ctx = document.getElementById('hi').getContext('2d');

        for(var i=0; i<m; i++) {
            ctx.beginPath();
            ctx.moveTo(segments[i][p[tt][i]-1][0], h-50-segments[i][p[tt][i]-1][1]);
            if(p[tt][i]<k) ctx.lineTo(segments[i][p[tt][i]][0], h-50-segments[i][p[tt][i]][1]);
            ctx.strokeStyle = '#58f'; //['#f00', '#0f0', '#00f'][i%3];
            ctx.lineWidth = 4;
            ctx.lineCap = 'round';
            ctx.lineJoin = 'round';
            ctx.stroke();
        }
        ctx.beginPath();
        ctx.moveTo(segments[actives[tt]][p[tt][actives[tt]]-1][0], h-50-segments[actives[tt]][p[tt][actives[tt]]-1][1]);
        ctx.lineTo(segments[actives[tt]][p[tt][actives[tt]]-0][0], h-50-segments[actives[tt]][p[tt][actives[tt]]-0][1]);
        ctx.strokeStyle = '#3f0';
        ctx.lineWidth = 4;
        ctx.lineCap = 'round';
        ctx.lineJoin = 'round';
        ctx.stroke();
        ctx.beginPath();
        ctx.moveTo(segments[actives[tt]][p[tt][actives[tt]]-1][0], h-50-segments[actives[tt]][p[tt][actives[tt]]-1][1]);
        ctx.lineTo(segments[actives[tt]][p[tt][actives[tt]]-0][0], h-50-segments[actives[tt]][p[tt][actives[tt]]-0][1]);
        ctx.lineTo(segments[actives[tt]][p[tt][actives[tt]]-0][0], 0);
        ctx.lineTo(segments[actives[tt]][p[tt][actives[tt]]-1][0], 0);
        ctx.closePath();
        ctx.fillStyle = 'rgba(80,200,40,0.2)';
        ctx.fill();

        // ctx.beginPath();
        // ctx.moveTo(env[tt+1][0], 0, 3, 0, Math.PI*2, true);
        // ctx.lineTo(env[tt+1][0], h, 3, 0, Math.PI*2, true);
        // ctx.strokeStyle = '#9af';
        // ctx.lineWidth = 1;
        // ctx.lineCap = 'round';
        // ctx.lineJoin = 'round';
        // ctx.stroke();
        // ctx.beginPath();
        // ctx.moveTo(env[tt][0], 0, 3, 0, Math.PI*2, true);
        // ctx.lineTo(env[tt][0], h, 3, 0, Math.PI*2, true);
        // ctx.strokeStyle = '#9af';
        // ctx.lineWidth = 1;
        // ctx.lineCap = 'round';
        // ctx.lineJoin = 'round';
        // ctx.stroke();
        ctx.beginPath();
        ctx.moveTo(env[tt+1][0], h-50-env[tt+1][1]);
        ctx.lineTo(env[tt][0], h-50-env[tt][1]);
        ctx.strokeStyle = '#f30';
        ctx.lineWidth = 4;
        ctx.lineCap = 'round';
        ctx.lineJoin = 'round';
        ctx.stroke();

        ctx.beginPath();
        ctx.arc(env[tt+1][0], h-50-env[tt+1][1], 3, 0, Math.PI*2, true);
        ctx.fillStyle = '#f30';
        ctx.closePath();
        ctx.fill();
        ctx.beginPath();
        ctx.arc(env[tt][0], h-50-env[tt][1], 3, 0, Math.PI*2, true);
        ctx.fillStyle = '#f30';
        ctx.closePath();
        ctx.fill();
    }
    II = window.setInterval(function() {
        if(playing) {
            tt = (tt+1)%p.length;
            draw();
        }
    }, 500);

    document.addEventListener("keydown", function keyDownTextField(e) {
        var keyCode = e.keyCode;
        if(keyCode === 39) {
            playing = false;
            tt = (tt+1)%p.length;
            draw();
        } else if(keyCode === 37) {
            playing = false;
            tt = (tt+p.length-1)%p.length;
            draw();
        } else if(keyCode === 27) {
            playing = false;
            simpledraw();
        }
    }, false);
</script>
???