Width and Bounding Box of Imprecise Points

Vahideh Keikha, Maarten Löffler, Ali Mohades, Zahed Rahmati

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationProc. 30th Canadian Conference on Computational Geometry
Publication statusPublished - 2018

Bibliographical note

(to appear)

Keywords

  • CG, IMP

Fingerprint

Dive into the research topics of 'Width and Bounding Box of Imprecise Points'. Together they form a unique fingerprint.

Cite this