INTERSECTION OF CONVEX OBJECTS IN TWO AND THREE DIMENSIONS.

Research output: Contribution to journalArticle

69 Scopus citations

Abstract

One of the basic geometric operations involves determining whether a pair of convex objects intersect. This problem is well understood in a model of computation in which the objects are given as input and their intersection is returned as output. For many applications, however, it may be assumed that the objects already exist within the computer and that the only output desired is a single piece of data giving a common point if the objects intersect or reporting no intersection if they are disjoint. For this problem, none of the previous lower bounds are valid and algorithms are proposed requiring sublinear time for their solution in two and three dimensions.

Original languageEnglish (US)
Pages (from-to)1-27
Number of pages27
JournalJournal of the ACM
Volume34
Issue number1
DOIs
StatePublished - Jan 1 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design
  • Hardware and Architecture
  • Information Systems
  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'INTERSECTION OF CONVEX OBJECTS IN TWO AND THREE DIMENSIONS.'. Together they form a unique fingerprint.

  • Cite this