Name
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. |
Year | DOI | Venue |
|---|---|---|
1986 | 10.1109/SFCS.1986.23 | FOCS |
Keywords | Field | DocType |
geometric application,fixed point,motion planning,davenport schinzel sequence,2-d polyhedral terrain,polygonal region,convex polygon,davenport-schinzel sequence,plane amidst polygonal barrier,efficient algorithm,following geometric problem,simple polygon,decision support systems,planning,algorithm design and analysis,data structures,upper bound,computational geometry,indexes,geometry,manganese,silicon,binary trees | Discrete mathematics,Combinatorics,Polygon,Disjoint sets,Computer science,Computational geometry,Convex polygon,Polyhedral terrain,Star-shaped polygon,Monotone polygon,Pointwise | Conference |
ISBN | Citations | PageRank |
0-8186-0740-8 | 17 | 3.50 |
References | Authors | |
13 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Micha Sharir | 1 | 8405 | 1183.84 |
| Richard Cole | 2 | 4527 | 505.61 |
| Klara Kedem | 3 | 1291 | 251.41 |
| Daniel Leven | 4 | 553 | 94.49 |
| Richard Pollack | 5 | 912 | 203.75 |
| Shmuel Sifrony | 6 | 322 | 55.35 |