SODA Conference 1999 Conference Paper
Locked and Unlocked Polygonal Chains in 3D
- Therese C. Biedl
- Erik D. Demaine
- Martin L. Demaine
- Sylvain Lazard
- Anna Lubiw
- Joseph O'Rourke
- Mark H. Overmars
- Steve Robbins
Author name cluster
Joseph O'Rourke
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
4 papers
2 author rows
Possible papers
4I&C Journal 1989 Journal Article
Finding minimal convex nested polygons
- Alok Aggarwal
- Heather Booth
- Joseph O'Rourke
- Subhash Suri
- Chee K. Yap
We consider the problem of finding a polygon nested between two given convex polygons that has a minimal number of vertices. Our main result is an O(n log k) algorithm for solving the problem, where n is the total number of vertices of the given polygons, and k is the number of vertices of a minimal nested polygon. We also present an O(n) sub-optimal algorithm, and a simple O(nk) optimal algorithm.
FOCS Conference 1983 Conference Paper
Constructing Arrangements of Lines and Hyperplanes with Applications
- Herbert Edelsbrunner
- Joseph O'Rourke
- Raimund Seidel
An optimal algorithm is presented for constructing an arrangement of hyperplanes in arbitrary dimensions. It relies on a combinatorial result that is of interest in its own right. The algorithm is shown to improve known worst-case time complexities for five problems: computing all order-k Voronoi diagrams, computing the λ-matrix, estimating halfspace queries, degeneracy testing, and finding the minimum volume simplex determined by a set of points.