Locating an obnoxious plane
| Autor: | José Miguel Díaz-Báñez, Joan Antoni Sellarès, Mario A. Lopez |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Convex hull
Information Systems and Management General Computer Science Euclidean space Plane (geometry) Annulus (mathematics) Management Science and Operations Research Largest empty sphere Industrial and Manufacturing Engineering Combinatorics Modeling and Simulation Duality (projective geometry) Line (geometry) Point (geometry) Mathematics |
| Zdroj: | European Journal of Operational Research. 173:556-564 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2005.02.048 |
| Popis: | Let S be a set of n points in three-dimensional Euclidean space. We consider the problem of positioning a plane π intersecting the convex hull of S such that min{d(π, p); p ∈ S} is maximized. In a geometric setting, the problem asks for the widest empty slab through n points in space, where a slab is the open region of R 3 that is bounded by two parallel planes that intersect the convex hull of S. We give a characterization of the planes which are locally optimal and we show that the problem can be solved in O(n3) time and O(n2) space. We also consider several variants of the problem which include constraining the obnoxious plane to contain a given line or point and computing the widest empty slab for polyhedral obstacles. Finally, we show how to adapt our method for computing a largest empty annulus in the plane, improving the known time bound O(n3 log n) [J.M. Diaz-Banez, F. Hurtado, H. Meijer, D. Rappaport, T. Sellares, The largest empty annulus problem, International Journal of Computational Geometry and Applications 13 (4) (2003) 317–325]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect