Optimally Decomposing Coverings with Translates of a Convex Polygon

Matt Gibson; Kasturi Varadarajan

doi:10.1007/s00454-011-9353-9

Back

Optimally Decomposing Coverings with Translates of a Convex Polygon

Journal article

Open access

Peer reviewed

Optimally Decomposing Coverings with Translates of a Convex Polygon

Matt Gibson and Kasturi Varadarajan

Discrete & computational geometry, Vol.46(2), pp.313-333

09/01/2011

DOI: 10.1007/s00454-011-9353-9

Files and links (1)

url

https://doi.org/10.1007/s00454-011-9353-9View

Published (Version of record) Open Access

Abstract

We show that any k-fold covering using translates of an arbitrary convex polygon can be decomposed into Omega(k) covers. Such a decomposition can be computed using an efficient (polynomial-time) algorithm.

Computer Science

Computer Science, Theory & Methods

Mathematics

Physical Sciences

Science & Technology

Technology

Details

Title: Subtitle: Optimally Decomposing Coverings with Translates of a Convex Polygon
Creators: Matt Gibson - University of Iowa
Kasturi Varadarajan - University of Iowa
Resource Type: Journal article
Publication Details: Discrete & computational geometry, Vol.46(2), pp.313-333
Publisher: Springer Nature
DOI: 10.1007/s00454-011-9353-9
ISSN: 0179-5376
eISSN: 1432-0444
Number of pages: 21
Language: English
Date published: 09/01/2011
Academic Unit: Computer Science
Record Identifier: 9984259407102771

Metrics

1 Record Views

13 Times Cited - Web of Science