On lines missing polyhedral sets in 3-space |
| |
Authors: | M Pellegrini |
| |
Institution: | 1. Department of Computer Science, King’s College, Strand, WC2R 2LS, London, England
|
| |
Abstract: | We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include: - An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
- AnO(n 1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
- An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
- An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n 4/3+ε+k 1/3 n 1+ε+klog2 n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. 5].
The tools used to obtain these results include Plücker coordinates of lines, random sampling, and polarity transformations in 3-space. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|