### Abstract

Perhaps the most important application of computer geometry involves determining whether a pair of convex objects intersect. This problem is well understood in a model of computation where the objects are given as input and their intersection is returned as output. However, for many applications, we may assume 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 we propose algorithms requiring sublinear time for their solution in 2 and 3 dimensions.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980 |

Publisher | Association for Computing Machinery |

Pages | 146-153 |

Number of pages | 8 |

ISBN (Electronic) | 0897910176 |

DOIs | |

State | Published - Apr 28 1980 |

Externally published | Yes |

Event | 12th Annual ACM Symposium on Theory of Computing, STOC 1980 - Los Angeles, United States Duration: Apr 28 1980 → Apr 30 1980 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 1980-April |

ISSN (Print) | 0737-8017 |

### Other

Other | 12th Annual ACM Symposium on Theory of Computing, STOC 1980 |
---|---|

Country | United States |

City | Los Angeles |

Period | 4/28/80 → 4/30/80 |

### All Science Journal Classification (ASJC) codes

- Software

## Fingerprint Dive into the research topics of 'Detection is easier than computation'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980*(pp. 146-153). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 1980-April). Association for Computing Machinery. https://doi.org/10.1145/800141.804662