Browse Prior Art Database

Efficient Algorithms for Enumerating Intersecting Intervals and Rectangles

IP.com Disclosure Number: IPCOM000128910D
Original Publication Date: 1980-Jun-01
Included in the Prior Art Database: 2005-Sep-20
Document File: 8 page(s) / 34K

Publishing Venue

Software Patent Institute

Related People

McCreight, E.: AUTHOR [+3]

Abstract

Let D be a dynamic set of intervals over the set 1,2,...,k of integers. Consider the following operations applied to D: (1) Insert an interval [ x,y ] into D. (2) Delete an interval [ x,y ] from D. (3) Given a test integer u, list those intervals [ x,y ] in D that contain u. (4) Given a test interval [ u,y ] , list those intervals [ x,y ] in D for which [ x,y ] n [ u,y ] is non"; empty. Using a new data structure that we call a tile tree, operations (1) and (2) can be implemented in O(n log (max{n,k})) time, where n is the cardinality of D. Operations (3) and (4) require at most O(n log (max{n,k})+s) time, where s is the number of intervals listed. The die tree occupies O(n) space. Using a previously-known plane-sweep technique, the operations above can be used to implement off-line algorithms to list all intersecting pairs of rectangles within a set of n aligned rectangles in O(n) space and O(n log n + s) time.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

©; Xerox Palo Alto Research Center, June, 1980

Efficient Algorithms for Enumerating Intersecting Intervals and Rectangles

by Edward M. McCreight

CSL-80 9 JUNE 1980
(I) Xerox Corporation 1980

Abstract: See next page.

A version of this paper has been submitted to SIAM Journal/ on Computing. CR Categories: 5.25, 3.74, 5.39

Key words and phrases: computational geometry, search trees, intersection, intervals, rectangles, concrete complexity.

XEROX

PALO ALTO RESEARCH CENTER 3333 Coyote Hill Road / Palo Alto / California 94304

Abstract:

Let D be a dynamic set of intervals over the set 1,2,...,k of integers. Consider the following operations applied to D:

(1) Insert an interval [ x,y ] into D.
(2) Delete an interval [ x,y ] from D.
(3) Given a test integer u, list those intervals [ x,y ] in D that contain u.
(4) Given a test interval [ u,y ] , list those intervals [ x,y ] in D for which [ x,y ] n [ u,y ] is non" empty.

Using a new data structure that we call a tile tree, operations (1) and (2) can be implemented in O(n log (max{n,k})) time, where n is the cardinality of D. Operations (3) and (4) require at most O(n log (max{n,k})+s) time, where s is the number of intervals listed. The die tree occupies O(n) space.

Using a previously-known plane-sweep technique, the operations above can be used to implement off-line algorithms to list all intersecting pairs of rectangles within a set of n aligned rectangles in O(n) space and O(n log n + s) time.

1. Introduction

Many computer applications involve sets of aligned rectangles: rectangles with their sides parallel to the co-ordinate axes. In such applications it frequently important to know which rectangles touch or overlap which other ones. For example, the samples" items of integrated circuit mask geometry are aligned rectangles. In order to do machine-aided geometric design rule checking or electrical circuit extraction, one needs algorithms that answer questions about which rectangles touch and overlap.

We present here a new data structure and associated algorithms for listing all intersecting pairs of rectangles within a set of n aligned rectangles in O(n) space and O(n log n + s) time, where s is the length of the output list. This result derives from a more basic result about time-varying

Xerox Corporation Page 1 Jun 01, 1980

Page 2 of 8

Efficient Algorithms for Enumerating Intersecting Intervals and Rectangles

sets of linear intervals, which is presented first. In each case there are two dimensions involved. With the rectangles, both dimensions are spatial, and there is no temporal dimension. With the time-varying sets of linear intervals, a spatial dimension is exchanged for a temporal sequence.

Let D be a dynamic set of intervals over the set 1,2,...,k of integers. Consider the following interval operations applied to D:
InsertInterval [ x,y ] : Insert an interval [ x,y ] into D.

DeleteInterval [ x,y ] : Delete an interva...