The minimum convex container of two convex polytopes under translations
| Autor: | Sang Won Bae, Otfried Cheong, Chan-Su Shin, Dongwoo Park, Judit Abardia, Hee-Kap Ahn, Susanna Dann |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Convex hull
Convex analysis Discrete mathematics 021103 operations research Control and Optimization 0211 other engineering and technologies Convex set 0102 computer and information sciences 02 engineering and technology Subderivative 01 natural sciences Computer Science Applications Combinatorics Computational Mathematics Computational Theory and Mathematics 010201 computation theory & mathematics Convex polytope Convex body Convex combination Geometry and Topology Orthogonal convex hull Mathematics |
| Zdroj: | Computational Geometry. 77:40-50 |
| ISSN: | 0925-7721 |
| DOI: | 10.1016/j.comgeo.2018.02.004 |
| Popis: | Given two convex d-polytopes P and Q in R d for d ⩾ 3 , we study the problem of bundling P and Q in a smallest convex container. More precisely, our problem asks to find a minimum convex set containing P and a translate of Q that do not properly overlap each other. We present the first exact algorithm for the problem for any fixed dimension d ⩾ 3 . The running time is O ( n ( d − 1 ) ⌊ d + 1 2 ⌋ ) , where n denotes the number of vertices of P and Q. In particular, in dimension d = 3 , our algorithm runs in O ( n 4 ) time. We also give an example of polytopes P and Q such that in the smallest container the translates of P and Q do not touch. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect