Efficient Computation of Crossing Components and Shortcut Hulls

Abstract

Polygon simplification is an important building block in many geovisualization algorithms. Recently, the concept of shortcut hulls was proposed to obtain a simplified polygon that fully contains the original polygon. Given a set of potential shortcuts between the polygon vertices, the computation of the optimal shortcut hull crucially relies on identifying edge crossings among the shortcuts and computing so called crossing components. In this paper, we present novel algorithms to significantly accelerate these steps. For a simple polygon P with n vertices and a set of shortcuts C, we describe an algorithm for computing all edge crossings in O(n+m+k), where m := |C| and k is the number of crossings. This output-sensitive algorithm is clearly optimal and a significant improvement over general-purpose algorithms to identify edge crossings. Furthermore, we extend this algorithm to compute the crossing components in O(min{n+m+k,n2}). As k could potentially be up to Θ(n4), this is a significant speed-up if only the crossing components are needed rather than each individual crossing. Finally, we propose a novel crossing component hierarchy data structure. It encodes the crossing components and allows to efficiently partition the polygon based thereupon. We show that our novel algorithms and data structures allow to significantly reduce the theoretical running time of shortcut hull computation.