TY - JOUR

T1 - How to cover a point set with a V-shape of minimum width

AU - Aronov, Boris

AU - Dulieu, Muriel

N1 - Funding Information:
Work on this paper has been supported by grant No. 2006/194 from the U.S.–Israel Binational Science Foundation and by NSF Grant CCF-08-30691 . Work by Boris Aronov has also been supported by NSA MSP Grant H98230-10-1-0210 . An extended abstract of this paper appeared in the Proceedings of the Algorithms and Data Structures Symposium (WADSʼ11) (Aronov and Dulieu, 2011 [7] ).

PY - 2013/4

Y1 - 2013/4

N2 - A balanced V-shape is a polygonal region in the plane contained in the union of two crossing equal-width strips. It is delimited by two pairs of parallel rays that emanate from two points x, y, are contained in the strip boundaries, and are mirror-symmetric with respect to the line xy. The width of a balanced V-shape is the width of the strips. We first present an O( n2logn) time algorithm to compute, given a set of n points P, a minimum-width balanced V-shape covering P. We then describe a PTAS for computing a (1+ε)-approximation of this V-shape in time O((n/ε)logn+(n/ ε3 /2) log2(1/ε)). A much simpler constant-factor approximation algorithm is also described.

AB - A balanced V-shape is a polygonal region in the plane contained in the union of two crossing equal-width strips. It is delimited by two pairs of parallel rays that emanate from two points x, y, are contained in the strip boundaries, and are mirror-symmetric with respect to the line xy. The width of a balanced V-shape is the width of the strips. We first present an O( n2logn) time algorithm to compute, given a set of n points P, a minimum-width balanced V-shape covering P. We then describe a PTAS for computing a (1+ε)-approximation of this V-shape in time O((n/ε)logn+(n/ ε3 /2) log2(1/ε)). A much simpler constant-factor approximation algorithm is also described.

KW - Approximation algorithm

KW - Computational metrology

KW - Curve reconstruction

KW - Fitting

KW - Geometric optimization

UR - http://www.scopus.com/inward/record.url?scp=84869094244&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84869094244&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2012.09.006

DO - 10.1016/j.comgeo.2012.09.006

M3 - Article

AN - SCOPUS:84869094244

SN - 0925-7721

VL - 46

SP - 298

EP - 309

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 3

ER -