### Abstract

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( ^{n2}logn) 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.

Original language | English (US) |
---|---|

Pages (from-to) | 298-309 |

Number of pages | 12 |

Journal | Computational Geometry: Theory and Applications |

Volume | 46 |

Issue number | 3 |

DOIs | |

State | Published - Apr 2013 |

### Keywords

- Approximation algorithm
- Computational metrology
- Curve reconstruction
- Fitting
- Geometric optimization

### ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics

## Fingerprint Dive into the research topics of 'How to cover a point set with a V-shape of minimum width'. Together they form a unique fingerprint.

## Cite this

*Computational Geometry: Theory and Applications*,

*46*(3), 298-309. https://doi.org/10.1016/j.comgeo.2012.09.006