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

Boris Aronov; John Iacono; Özgür Özkan; Mark Yagnatinsky

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

Boris Aronov, John Iacono, Özgür Özkan, Mark Yagnatinsky

Research output: Contribution to conference › Paper › peer-review

Abstract

A V-shape is an infinite polygonal region bounded by two pairs of parallel rays emanating from two vertices (see Figure 1). We describe a randomized algorithm that, given n points and an integer k ≥ 0, finds the minimum-width V-shape enclosing all but k of the points with probability 1 - 1/n^c for any c > 0, with expected running time O(cn²(k + 1)⁴ log n(log n log log n + k)).

Original language	English (US)
Pages	211-215
Number of pages	5
State	Published - 2013
Event	25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada Duration: Aug 8 2013 → Aug 10 2013

Other

Other	25th Canadian Conference on Computational Geometry, CCCG 2013
Country/Territory	Canada
City	Waterloo
Period	8/8/13 → 8/10/13

ASJC Scopus subject areas

Geometry and Topology
Computational Mathematics

Cite this

@conference{a665ecd1d93148a5bdb235cfe4dab611,

title = "How to cover most of a point set with a V-shape of minimum width",

abstract = "A V-shape is an infinite polygonal region bounded by two pairs of parallel rays emanating from two vertices (see Figure 1). We describe a randomized algorithm that, given n points and an integer k ≥ 0, finds the minimum-width V-shape enclosing all but k of the points with probability 1 - 1/nc for any c > 0, with expected running time O(cn2(k + 1)4 log n(log n log log n + k)).",

author = "Boris Aronov and John Iacono and {\"O}zg{\"u}r {\"O}zkan and Mark Yagnatinsky",

year = "2013",

language = "English (US)",

pages = "211--215",

}

TY - CONF

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

AU - Aronov, Boris

AU - Iacono, John

AU - Özkan, Özgür

AU - Yagnatinsky, Mark

PY - 2013

Y1 - 2013

N2 - A V-shape is an infinite polygonal region bounded by two pairs of parallel rays emanating from two vertices (see Figure 1). We describe a randomized algorithm that, given n points and an integer k ≥ 0, finds the minimum-width V-shape enclosing all but k of the points with probability 1 - 1/nc for any c > 0, with expected running time O(cn2(k + 1)4 log n(log n log log n + k)).

AB - A V-shape is an infinite polygonal region bounded by two pairs of parallel rays emanating from two vertices (see Figure 1). We describe a randomized algorithm that, given n points and an integer k ≥ 0, finds the minimum-width V-shape enclosing all but k of the points with probability 1 - 1/nc for any c > 0, with expected running time O(cn2(k + 1)4 log n(log n log log n + k)).

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

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

M3 - Paper

AN - SCOPUS:84961370711

SP - 211

EP - 215

T2 - 25th Canadian Conference on Computational Geometry, CCCG 2013

Y2 - 8 August 2013 through 10 August 2013

ER -

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

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this