Geometric applications of Davenport-Schinzel sequences
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 77-86
- https://doi.org/10.1109/sfcs.1986.23
Abstract
We present efficient algorithms for the following geometric problems: (i) Preprocessing of a 2-D polyhedral terrain so as to support fast ray shooting queries from a fixed point. (ii) Determining whether two disjoint interlocking simple polygons can be separated from one another by a sequence of translations. (iii) Determining whether a given convex polygon can be translated and rotated so as to fit into another given polygonal region. (iv) Motion planning for a convex polygon in the plane amidst polygonal barriers. All our algorithms make use of Davenport Schinzel sequences and on some generalizations of them; these sequences are a powerful combinatorial tool applicable in contexts which involve the calculation of the pointwise maximum or minimum of a collection of functions.Keywords
This publication has 16 references indexed in Scilit:
- Fractional cascading: A data structuring technique with geometric applicationsPublished by Springer Nature ,2005
- Searching and storing similar listsJournal of Algorithms, 1986
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstaclesDiscrete & Computational Geometry, 1986
- Making data structures persistentPublished by Association for Computing Machinery (ACM) ,1986
- An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstaclesPublished by Association for Computing Machinery (ACM) ,1985
- Movable Separability of SetsPublished by Elsevier ,1985
- An algorithm for planning collision-free paths among polyhedral obstaclesCommunications of the ACM, 1979
- On a problem of Davenport and SchinzelActa Arithmetica, 1973
- A combinatorial problem connected with differential equations IIActa Arithmetica, 1970
- A Combinatorial Problem Connected with Differential EquationsAmerican Journal of Mathematics, 1965