### Abstract

Efficient algorithms are presented for the following geometric problems: (1) Preprocessing of a 2-D polyhedral terrain so as to support fast ray shooting queries from a fixed point. (2) Determining whether two disjoint interlocking simple polygons can be separated from one another by a sequence of translations. (3) Determining whether a given convex polygon can be translated and rotated so as to fit into another given polygonal region. (4) Motion planning for a convex polygon in the plane amidst polygonal barriers. All the algorithms make use of Davenport-Schinzel sequences and their generalizations; these sequences are a powerful combinatorial tool applicable in contexts that involve the calculation of the pointwise maximum or minimum of a collection of functions.

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

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Pages | 77-86 |

Number of pages | 10 |

DOIs | |

State | Published - 1986 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### ASJC Scopus subject areas

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'GEOMETRIC APPLICATIONS OF DAVENPORT-SCHINZEL SEQUENCES.'. Together they form a unique fingerprint.

## Cite this

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 77-86). (Annual Symposium on Foundations of Computer Science (Proceedings)). https://doi.org/10.1109/SFCS.1986.23