🚀 go-pugleaf

           Department of Computer Science, University of Toronto
         (SF = Sandford Fleming Building, 10 King's College Road)

       -------------------------------------------------------------

                              GRAPHICS/THEORY
               SF1101, at 3:00 p.m., Tuesday 19 January 1993

                               Jack Snoeyink
      Department of Computer Science, University of British Columbia

                            " Maps & Puzzles "

In this talk we'll investigate how a simple geometric fact---that convex
objects in the plane can be sorted by "aboveness"---affects the computation
and display of maps and puzzles.

Many geographic information systems organize maps into different layers and
create new maps by solving the "polygon overlay problem."  We can abstract
this as a simple geometric intersection problem---given sets of n disjoint
red segments and n disjoint blue segments, compute the red/blue
intersections.  We use aboveness to derive a simple data structure and
storage organization that solves the abstract problem optimally (reporting
all K intersections in O(n log n + K) time or counting in O(n log n) time)
and discuss implications for the overlay problem.

The aboveness order, which is so useful in the plane, breaks in three
dimensions.  This is clear from the need to cut objects to draw them from
back to front using the "painter's algorithm."  In fact, we'll show a
configuration where the objects cannot be split into two sets, one above
the other, no matter which way is up.  This also has implications for
assembly planning.