@inproceedings{9bc873260c5b4e01b4671f40bf93446a,
title = "GEOMETRIC APPLICATIONS OF DAVENPORT-SCHINZEL SEQUENCES.",
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.",
author = "Micha Sharir and Richard Cole and Klara Kedem and Daniel Leven and Richard Pollack and Shmuel Sifrony",
year = "1986",
doi = "10.1109/SFCS.1986.23",
language = "English (US)",
isbn = "0818607408",
series = "Annual Symposium on Foundations of Computer Science (Proceedings)",
pages = "77--86",
booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",
}