Width and Bounding Box of Imprecise Points

In this paper we study the following problem: we are given a set L of parallel line segments, and we wish to find a set P containing one point from each segment such that we maximize/minimize the width of P or the area of the bounding box of P among all possible choices for P. We design an approximation algorithm for computing the largest width. We also show that the smallest width and the smallest bounding box can be computed in quadratic time. We then proceed to present a polynomial time dynamic programming algorithm for computing the largest-area bounding box. We also present an FPTAS for this problem.

keywords: Computational Geometry, Data Imprecision

Conference Proceedings (peer-reviewed)

Ali Mohades, Maarten Lรถffler, Vahideh Keikha, Zahed Rahmati
Width and Bounding Box of Imprecise Points
Proc. 30th Canadian Conference on Computational Geometry
, 2018
http://www.cs.umanitoba.ca/~cccg2018/papers/session3B-p3.pdf

back to list