Marco Pellegrini
ABSTRACT
We study some combinatorial and algorithmic problems on sets of lines and polyhedral objects in 3-space. Our main results include:
An O(n32c√log n) upper bound on the worst case complexity of the set of lines missing a star-shaped compact polyhedron with n edges.
Given a tar-shaped compact polyhedron P with n edges we can compute on-line the shadow of P from a query direction v in almost-optimal ouput-sensitive time O(k log4 n), where k is the size of the shadow. The storage used by the data structure is O(n3+ϵ)
An O(n32c√log n) upper bound on the worst case complexity of the set of lines that can be moved to infinity without the intersecting of a set of n given lines. This bound is almost tight.
An O(n1.5 + ϵ) ranmdomized expected time algorithm that tests the separation property: there exists a direction v along which a set of n red lines can be tranlated away from a set of n blue lines without collsions?
Computing the intersection of two polyhedral terrains in 3-space with n edges in time O(n4/3 + ϵ + k1/3n1+ϵ + k log2 n), where k is the size of the output, and ϵ > 0 an arbitrary small but fixed constant. This algorithm improves on the best previous result of the Chazelle at al. [7].
The tools used to obtain these results include Plücker coordinates of lines, random sampling and polarity transformations in 3-space.
- 1.P. Agarwal. Personal communication. January 1992.Google Scholar
- 2.P. Agarwal and J. Matou~ek. Ray shooting and parametric search. In Proceedings of the 2dth Annual A CM Symposium on Theory of Computing, pages 517-526, 1992. Google ScholarDigital Library
- 3.P. K. Agarwal and M. Sharir. Applications of a new space partitioning technique. In Proceedings of the 1991 Workshop on Algorithms and Data Structures, number 519 in Lecture Notes in Computer Science, pages 379-391. Springer Verlag, 1991.Google Scholar
- 4.B. Aronov and M. Sharir. Triangles in space or building (and analyzing) castles in the air. Combinatorica, 10(2):137-173, 1990.Google Scholar
- 5.B. Aronov and M. Sharir. Castles in the air revisited. In Proceedings of the 8th A CM Symposium on Computalional Geometry, pages i46- 2513, 1992. Google ScholarDigital Library
- 6.B. Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra. Ill Proceedings of the 30ih IEEE Symposium on Foundations of Computer Science, pages 586-591, 1989.Google ScholarDigital Library
- 7.B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Lines in space: combinatorics, algorithms and applications. In Proc. of the 21st Symposium on Theory of Computing, pages 382- 393, 1989. Google ScholarDigital Library
- 8.B. Chazelle, H. Edelsbrunner, L. Guibas, and M Sharir. Algorithms for bichromatic line segments problems and polyhedral terrains. To appear in A lgorithmica. Also Tech. Rep. UIUCDCS-R-90-1578, University of Illinois at Urbana Champaign, Dept. of Comp. Sci., 1990.Google Scholar
- 9.B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Diameter, width, closest line pair and parametric search. In Proceedings of the $th A CM Symposium on Computational Geometry, pages 120-129, 1992. Google ScholarDigital Library
- 10.B. Chazelle, T. Ottman, E. Soisalon-Soininen, and D. Wood. The complexity of decidability of separation, in Proceedings of the 11th International Colloquium on Automata, Programming, and Languages, pages 125-134, 1984. Google ScholarDigital Library
- 11.K. Clarkson. New applications of random sampiing in computational geometry. Discrete G Computational Geometry, 2:195-222, 1987.Google ScholarDigital Library
- 12.M. de Berg, D. Halperlin, M. Overmars, J. Snoeyink, and M. van Kreveld. Efficient rayshooting and hidden surface removal. In Proceedings of the 7th A CM Symposium on Computational Geometry, pages 21-30, 1991. Google ScholarDigital Library
- 13.M. de Berg, D. Halperlin, M. Overmars, and M. van Kreveld. Sparse arrangements and the number of views of polyhedral scenes. Manuscript, June 1992.Google Scholar
- 14.H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer Verlag, 1987. Google ScholarDigital Library
- 15.H. Edelsbrunner, L. Guibas, and M. Sharir. The complexity and construction of many faces in arrangements of lines and segments. Discrete Computational Geometry, 5:161-196, 1990.Google ScholarDigital Library
- 16.J. Guibas and F. Yao. On translating sets of rectangles. In Proceedings of the 12th Annual A CM Symposium on Theory of Computing, pages 154-160, 1980. Google ScholarDigital Library
- 17.J. Matou~ek. Construction of e-nets. In Proceedings of the 5th A CM Symposium on Computational Geometry, pages 1-10, 1989. Google ScholarDigital Library
- 18.J. MatouSek. Cutting hyperplane arrangements. In Proceedings of the 6th ACM Symposium on Computational Geometry, pages 1-9, 1990. Google ScholarDigital Library
- 19.J. Matougek. Reporting points in halfspaces. In Proceedings of the 32th IEEE Symposium on Foundations of Computer Science, pages 207- 215, 1991. Google ScholarDigital Library
- 20.B. Natarajan. On planning assemblies, in Proceedings of the dth A CM Symposium on Computational Geometry, pages 299-308, 1988. Google ScholarDigital Library
- 21.O. Nurmi. On translating a set of objects in 2- and 3-dimensional space. Computer Vision, Graphics, and Image Processing, 36:42-52, 1986. Google ScholarDigital Library
- 22.O. Nurmi and J. Sack. Separating a polyhedron by one translation from a set of obstacles. In J. van Leeuwen, editor, Proc. Workshop on Graph-Theoretic Concepts in Computer Science, volume 344 of Lecture Notes in Computer Science, pages 202-212, 1988. Google ScholarDigital Library
- 23.D. Nussbaum and J. Sack. Translation separability of polyhedra. In Abstracts of the first Canadian Conference on Computational Geometry, page 34, 1989.Google Scholar
- 24.M. Pellegrini. Stabbing and ray shooting in 3- dimensional space. In Proceedings of the 6th A CM Symposium on Computational Geometry, pages 177-186, 1990. Google ScholarDigital Library
- 25.M. Pellegrini. Ray shooting on triangles in 3- space. A lgorithmica. To appear. Prelim. vers. in Lecture Notes in Computer Science number 519, pages 20-31, 199t.Google Scholar
- 26.M. Pellegrini. Incidence and nearest-neighbor problems for lines in 3-space. In Proceedings of the 8th A CM Symposium on Computational Geometry, pages 130-137, 1992. Google ScholarDigital Library
- 27.M. Pellegrini and P. Shot. Finding stabbing lines in 3-space. Discrete 64 Computational Geometry, 8:191-208, 1992.Google Scholar
- 28.R. Pollack, M. Sharir, and S. Sifrony. Separating two simple polygons by a sequence of translations. Discrete ~ Computational Geometry, 3:123-136, 1988.Google Scholar
- 29.F. Preparata and M. Shamos. Computational Geometry: an Introduction. Springr Verlag, 1985. Google ScholarDigital Library
- 30.F. Preparata and R. Tamassia. Efficient spatial point location. In Proceedings of the 1989 Workshop on Algorithms and Data Structures, pages 3-11, 1989. Google ScholarDigital Library
- 31.J. Reif and S. Sen. An efficient output-sensitive hidden-surface removal algorithm and its parallelization. In Proceedings of the Jib A CM Symposium on Computational Geometry, pages 193- 200, 1988. Google ScholarDigital Library
- 32.J. Schwartz and M. Sharir. A survey of motion planning and related geometric algorithms. In D. Kapur and J. Mundy, editors, Geometric Reasoning, pages 157-169. The MIT press, 1989. Google ScholarDigital Library
- 33.G. Toussaint. Movable separability of sets. In G. Toussaint, editor, Computational Geometry, pages 335-375. North-Holland, 1985.Google ScholarCross Ref
Index Terms
- On lines missing polyhedral sets in 3-space
Recommendations
On lines missing polyhedral sets in 3-space
We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:(1)An $$O(n^3 2^{c\sqrt {\log n} } )$$ upper bound on the worst-case complexity of the set of lines that can be ...
Polyhedral line transversals in space
Algorithms are developed for determining if a set of polyhedral objects inR3 can be intersected by a common transversal (stabbing) line. It can be determined inO(n logn) time if a set ofn line segments in space has a line transversal, and such a ...
Relationships Between Polyhedral Convex Sets and Generalized Polyhedral Convex Sets
AbstractIn this paper, we study some relationships between polyhedral convex sets and generalized polyhedral convex sets. In particular, we clarify by a counterexample that the necessary and sufficient conditions for the separation of a convex set and a ...
Comments