Browse Prior Art Database

ON THE DUALITY OF INTERSECTIONS AND CLOSEST POINTS

IP.com Disclosure Number: IPCOM000148322D
Original Publication Date: 1983-Aug-31
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Bajaj, C.: AUTHOR [+3]

Abstract

0. TEX DUAJ.I'II OF IRIIISfCTIOHS MB CLOSEST POIEIS

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 16

0. TEX DUAJ.I'II OF IRIIISfCTIOHS

MB CLOSEST POIEIS

C.. Bajaj and M. L i TR 83-568

August 1983

Department of Computer Science Cornell University
Ilthaca,
New York 14853

'T~LS

research was supported in part by NSF grant MCS81-01220.

[This page contains 1 picture or other non-text object]

Page 2 of 16

[This page contains 1 picture or other non-text object]

Page 3 of 16

On the Duality of Intersections and Closest Points t Chanderjit Bajaj and Ming Li

Department of Computer Science, Cornell University, Ithaca, NY 14853.

ABSTRACT

   We call the common intersection of k objects a k-intersection. We address questions of the form: Given n objects in the plane,'Does there exist a k-intersection ?', 'How many such k- intersections exist ?' and 'What is the maximum value of k for which there exists a k-intersection ?'. In answering such questions we utilize a duality that exists between k-intersections and k-closest points (the k points with the smallest enclosing circle), in that as
long as k points are close enough to be enclosed by a circle of radius r, the common intersection of k circles of radius r centered at each of those k points (i.e. their k-intersection) is non - null. A technique, dubbed 'rotation sorting' is them developed to provide efficient solutions to dual questions of the form: Given n points in the plane, 'Does there exist a set of k points which can be covered by a circle of radius r?', 'How many such sets of k points exist ?', and 'What are the maximum number of points that can be enclosed by a circle of radius r 1'.

   A similar duality between the intersection of a line with circles and the proximity of this line to the centers of the circles is exploited to obtain efficient algorithms for the transversals of circles in the plane. Extensions of the above questions to three and higher dimensions are also addressed, alongwith problems concerning unequal sized objects. Further certain generalisations of k- intersections and of the number of points enclosed by k objects in two dimensions and higher are shown to be NP-complete and DP-

complete.

t This research was supported in part by NSF grant MCS81-01220.

[This page contains 1 picture or other non-text object]

Page 4 of 16

[This page contains 1 picture or other non-text object]

Page 5 of 16

On the Duality of Intersections and Closest Points t

Chanderjit Bajaj and Ming Li

Department of Computer Science, Cornell University,

Ithaca, NY 14853.

1. Introduction

   This paper tries to relate questions about the intersection of objects with that involving the 'closeness' of points in a finite set. Calling the common inter- section of k objects a k-intersection we concern ourselves specifically with ques- tions of finding whether there exists a set of k objects, out of a finite set n, hav- ing a k-intersection? and the maximum value of k for which there exists such k-
in...