Intersection of convex objects in two and three dimensions
- 1 January 1987
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 34 (1) , 1-27
- https://doi.org/10.1145/7531.24036
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.Keywords
This publication has 7 references indexed in Scilit:
- Fast detection of polyhedral intersectionTheoretical Computer Science, 1983
- Plane-sweep algorithms for intersecting geometric figuresCommunications of the ACM, 1982
- Algorithms for Reporting and Counting Geometric IntersectionsIEEE Transactions on Computers, 1979
- Divide and conquer for linear expected timeInformation Processing Letters, 1978
- Finding the intersection of two convex polyhedraTheoretical Computer Science, 1978
- Multidimensional Searching ProblemsSIAM Journal on Computing, 1976
- Sequential minimax search for a maximumProceedings of the American Mathematical Society, 1953