The minimum convex container of two convex polytopes under translations

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 73
  • Download : 0
Given two convex d-polytopes P and Q in for , 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 . The running time is , where n denotes the number of vertices of P and Q. In particular, in dimension , our algorithm runs in 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.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2019-03
Language
English
Article Type
Article; Proceedings Paper
Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.77, pp.40 - 50

ISSN
0925-7721
DOI
10.1016/j.comgeo.2018.02.004
URI
http://hdl.handle.net/10203/250083
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0