Frank Staals

Date: 16:00 – 16:30, Thursday, 15.04.2021
Location: MS Teams ICS Colloquium

Title: Data Structures for Maintaining Growing Squares and Disks
Abstract: We consider data structures to maintain a dynamic set S of disjoint growing shapes –in particular squares and disks– and the pair of shapes from S that will start to intersect first. We show that this is the key ingredient in two applications:

In the first application, originating from geo-visualization, we wish to provide an interactive map that shows additional information using disjoint labels or glyphs. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs.

In the second application, originating from geographic information systems, we wish to maintain approximate locations of a set of moving entities and uniquely identify each entity. For each moving entity we maintain a region known to contain the entity. The size and location of these uncertainty regions varies over time.

We describe these applications in more detail, how our data structures support these applications, and the key ideas and challenges in the design of the data structures themselves.