Mikhail J. Atallah, Danny Z. Chen

CERIAS TR 2005-34

inproceedings

We present efficient algorithms for the problems of matching red and blue disjoint geometric obstacles in the plane and connecting the matched obstacle pairs with mutually nonintersecting paths that have useful geometric properties. We first consider matching n red and n blue disjoint rectilinear rectangles and connecting the n matched rectangle pairs with nonintersecting monotone rectilinear paths; each such path consists of O(n) segments and is not allowed to touch any rectangle other than the matched pair that it is linking. Based on a numbering scheme for certain geometric objects and on several useful geometric observations, we develop an O(n log n) time, O(n) space algorithm that produces a desired matching for rectilinear rectangles. If an explicit printing of all the n paths is required, then our algorithm takes O(n logn+L) time and O(n) space, where L is the total size of the desired output. We then extend these matching algorithms to other classes of red/blue polygonal obstacles. The numbering scheme also finds applications to other problems.

PDF

2001

International Journal of Computational Geometry & Applications

Atallah

World Scientific Publishing Company

Purdue University

2001-01-01

I. Introduction II. Preliminaries III. Partitioning Rectilinear Rectangles with a Staircase IV. Data Structures V. The Matching Algorithm for Rectangles VI. Reporting the Actual Paths VII. Extensions to Monotone Polygonal Obstacles VIII. Lower Bounds for the Matching Problems IV. Further Remarks

rectilinear paths, red/blue matching, numbering scheme, staircase separators

English

A hard-copy of this is in the CERIAS Library

Rectilinear paths, red/blue matching