License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.25
URN: urn:nbn:de:0030-drops-115211
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11521/
Bae, Sang Won
Minimum-Width Double-Strip and Parallelogram Annulus
Abstract
In this paper, we study the problem of computing a minimum-width double-strip or parallelogram annulus that encloses a given set of n points in the plane. A double-strip is a closed region in the plane whose boundary consists of four parallel lines and a parallelogram annulus is a closed region between two edge-parallel parallelograms. We present several first algorithms for these problems. Among them are O(n^2) and O(n^3 log n)-time algorithms that compute a minimum-width double-strip and parallelogram annulus, respectively, when their orientations can be freely chosen.
BibTeX - Entry
@InProceedings{bae:LIPIcs:2019:11521,
author = {Sang Won Bae},
title = {{Minimum-Width Double-Strip and Parallelogram Annulus}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {25:1--25:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11521},
URN = {urn:nbn:de:0030-drops-115211},
doi = {10.4230/LIPIcs.ISAAC.2019.25},
annote = {Keywords: geometric covering, parallelogram annulus, two-line center, double-strip}
}
|
Keywords: |
|
geometric covering, parallelogram annulus, two-line center, double-strip |
|
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
28.11.2019 |
