A (1+ ε)-approximation algorithm for 2-line-center

Pankaj K Agarwal; Cecilia M Procopiuc; Kasturi R Varadarajan

doi:10.1016/S0925-7721(03)00017-8

Back

A (1+ ε)-approximation algorithm for 2-line-center

Journal article

Open access

Peer reviewed

A (1+ ε)-approximation algorithm for 2-line-center

Pankaj K Agarwal, Cecilia M Procopiuc and Kasturi R Varadarajan

Computational geometry : theory and applications, Vol.26(2), pp.119-128

2003

DOI: 10.1016/S0925-7721(03)00017-8

Files and links (1)

url

https://doi.org/10.1016/S0925-7721(03)00017-8View

Published (Version of record) Open Access

Abstract

We consider the following instance of projective clustering, known as the 2-line-center problem: Given a set S of n points in R 2 , cover S by two congruent strips of minimum width. Algorithms that find the optimal solution for this problem have near-quadratic running time. In this paper we present an algorithm that, for any ε>0, computes in time O( n(log n+ ε −2log(1/ ε))+ ε −7/2log(1/ ε)) a cover of S by two strips of width at most (1+ε)w ∗ .

2-line-center problem

Approximation algorithms

Projective clustering

Shape fitting

Details

Title: Subtitle: A (1+ ε)-approximation algorithm for 2-line-center
Creators: Pankaj K Agarwal - Duke University
Cecilia M Procopiuc - AT&T (United States)
Kasturi R Varadarajan - University of Iowa
Resource Type: Journal article
Publication Details: Computational geometry : theory and applications, Vol.26(2), pp.119-128
DOI: 10.1016/S0925-7721(03)00017-8
ISSN: 0925-7721
eISSN: 1879-081X
Publisher: Elsevier B.V
Language: English
Date published: 2003
Academic Unit: Computer Science
Record Identifier: 9984259460802771

Metrics

35 Record Views

13 Times Cited - Web of Science