Divide-and-conquer in planar geometry

Abstract

In the last few years line-sweep has become the standard method to solve problems that involve computing some property of a set of planar objects. In this paper we argue that at least for sets of orthogonal objects divide-and-conquer is competitive, if a suitable representation of the objects is used. We support this claim by sketching three (new) time-optimal divide-and-conquer algorithms to solve the line segment intersection problem, the measure problem and the contour problem, respectively. It turns out that divide-and-conquer requires simpler supporting data structures while line-sweep permits an easier reduction to a one-dimensional problem.

Keywords:

• Algorithm design
• line-sweep
• divide-and-conquer
• rectangles
• intersection
• measure problem
• contour problem

C.R. Categories:

• F.2.2
• I.3.5