**Reading**PAGE

### Peer Evaluation activity

Views | 442 |

### Total impact ?

#### Send a

### Matthew has...

Trusted | 0 |

Reviewed | 0 |

Emailed | 0 |

Shared/re-used | 0 |

Discussed | 0 |

Invited | 0 |

Collected | 0 |

### This was brought to you by:

# Followblock this user
Matthew Cook
*Trusted member*

## Assistant Professor

Institute of Neuroinformatics, University of Zurich and ETH Zurich

Visiting Associate, Caltech

University of Zurich and ETH Zurich, Institute of Neuroinformatics

# A Geometric Theorem for Approximate Disk Covering Algorithms

## Oh la la

Your session has expired but *don’t worry*, your message

has been saved.Please log in and we’ll bring you back

to this page. You’ll just need to click “Send”.

**Your evaluation**is of great value to our authors and readers. Many thanks for your time.

Your **mailing list** is currently empty.

It will build up as you send messages

and links to your peers.

__No one__besides you has access to this list.

__Note__: Peer Evaluation will NOT store these email addresses log in

Your message has been sent.

### Description

**Title**: A Geometric Theorem for Approximate Disk Covering Algorithms

**Abstract**: We present a basic theorem in combinatorial geometry that leads to a family of approximation algorithms for the the geometric disk covering problem. These algorithms exhibit constant approximation factors, with a wide range of their choices. This exibility allows to achieve a running time that compares favourably with those of existing procedures. 1 Introduction and Main Results In this paper we present a basic theorem in combinatorial geometry and discuss its application to the well known problem of computing a geometric disk covering [1]. The theorem states as follows: Theorem 1 Consider a square lattice where the distance between two neighboring lattice vertices is one. Call a disk of xed radius r , centered at a lattice vertex, a grid disk. The number N of grid disks that are necessary and sucient to cover any disk of radius r placed on the plane, is given by: CASE 1. For r < p 2 2 , N does not exist. CASE 2. For p 2 2 r < p 10 4 , N = 6. CASE 3. For p 10 4...

**Subject**: unspecified

**Area**: Computer Science

**Language**: English

Affiliations : |

**Url**: http://vigeland.paradise.caltech.edu/papers/etr035.ps

**Doi**: 10.1.1.26.4042

### Leave a comment

### This contribution has not been reviewed yet. review?

You may receive the Trusted member label after :

• Reviewing **10 uploads**, whatever the media type.

• Being trusted by **10 peers**.

• If you are blocked by **10 peers** the "Trust label" will be suspended from your page. We encourage you to contact the administrator to contest the suspension.

#### Please select an affiliation to sign your evaluation:

#### Please select an affiliation:

### Matthew's * Peer Evaluation activity*

Views | 442 |

- 70Tournament sequences and Meeussen sequences, Electron
- 66It Takes Two Neurons To Ride a Bicycle
- 62The Reusable Symbol Problem
- 60Percolation in multi-hop wireless networks
- 59Programmability of Chemical Reaction Networks
- 59Self-healing Tile Assembly Model
- 55A Geometric Theorem for Approximate Disk Covering Algorithms
- 3Optimal ?-interleaving on tori
- 2A Geometric Theorem for Wireless Network Design Optimization�, http://www.paradise.caltech.edu/ ?massimo/homepage/papers/covering.ps
- 2Ad hoc wireless networks with noisy links
- 2COMBINING SELF-HEALING AND PROOFREADING IN SELF-ASSEMBLY
- 2Continuum percolation with unreliable and spread out connections

### Matthew* has...*

Trusted | 0 |

Reviewed | 0 |

Emailed | 0 |

Shared/re-used | 0 |

Discussed | 0 |

Invited | 0 |

Collected | 0 |

## Full Text request

### Your request will be sent.

Please enter your email address to be notified

when this article becomes available

**Your email**