Browse Prior Art Database

VERY FAST ALGORITHMS FOR THE; AREA OF THE UNION OF MANY CIRCLES

IP.com Disclosure Number: IPCOM000128246D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 29K

Publishing Venue

Software Patent Institute

Related People

Paul G. Spirakis: AUTHOR [+3]

Abstract

We present here an 0(n2) deterministic and an 0(n) probabilistic algorithm for computing the area of the union of n given circles. The accuracy of the probabilistic algorithm is controlled by the algorithm implementer (it can be set up to any desirable value). The , probabilistic algorithm is optimal in the sense that 0(n) time is needed to compute the sum of n real numbers, under quite general models of computation. The probabilistic linear algorithm can be extended, in a straightforward manner, to compute the volume of the union of many similar objects (e.g. spheres) in k dimensions. Its time complexity is then 0(nk). Our proof of fast convergence of the probabilistic method benefited a lot from a recent work of R. Karp and M. Luby on reliability. Our technique was also motivated by Karp and Luby's work, and some of our notation is heavily affected by their notation. L

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

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

VERY FAST ALGORITHMS FOR THE; AREA OF THE UNION OF MANY CIRCLES

BY

Paul G. Spirakis* December 1983

``' Report #98 ~~,r ~.~ *This work was supported in part by the National Science Foundation Grant NSF-MCS83-00630.

ABSTRACT

We present here an 0(n2) deterministic and an 0(n) probabilistic algorithm for computing the area of the union of n given circles. The accuracy of the probabilistic algorithm is controlled by the algorithm implementer (it can be set up to any desirable value). The , probabilistic algorithm is optimal in the sense that 0(n) time is needed to compute the sum of n real numbers, under quite general models of computation. The probabilistic linear algorithm can be extended, in a straightforward manner, to compute the volume of the union of many similar objects (e.g. spheres) in k dimensions. Its time complexity is then 0(nk). Our proof of fast convergence of the probabilistic method benefited a lot from a recent work of R. Karp and M. Luby on reliability. Our technique was also motivated by Karp and Luby's work, and some of our notation is heavily affected by their notation. L

1. Introduction

The problem of estimating the area of the union of many circles in the plane was first posed by [Shamos, 78]. We present here an 0(n2)

' deterministic and an 0(n) probabilistic algorithm for solving the

problem. The recent work of [Karp, Luby, 83] on estimating the failure y probability of an n- component system helped us a lot in stating the algorithm and formulating the proof of fast convergence. The probabilistic algorithm can be modified to compute the area of the union of other planar objects (of fixed description) e.g. triangles or boxes. The time is again 0(n). The algorithm can also be extended to compute the volume of the union of n spheres in k dimensions, in time 0(nk). The algorithm has similar time complexity for k-dimensional objects other than spheres, provided that each object has a fixed description (not dependent on n). A very recent work of [Sharir, 83] can be extended to provide an 0(n log2n) deterministic algorithm for computing the area of the union of n circles in the plane. The idea does not generalize easily to 3 dimensions. No efficient algorithms for the problem of computing volumes of unions of objects in more than 2 dimensions were presented in the past.

' 2. The problem in 2 dimensions

New York University Page 1 Dec 31, 1983

Page 2 of 12

VERY FAST ALGORITHMS FOR THE; AREA OF THE UNION OF MANY CIRCLES

2.1 General remarks v

The input is a list of n triples

(Equation Omitted)

where

(Equation Omitted)

are the Cartesian coordinates of the center of the circle Ci. n of radius ri. The problem is to compute the area of the union

(Equation Omitted)

Let U be the area of the union. Let E(Ci) denote the area of the n circle

(Equation Omitted)

The part of the plane covered by the i=1 union of the n circles is partitioned into nonoverlapping segments...