Micha Sharir, Richard Cole, Klara Kedem, Daniel Leven, Richard Pollack, Shmuel Sifrony

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
Number of pages10
StatePublished - 1986

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this