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 -