Simple Linear Time Algorithms For Piercing Pairwise Intersecting Disks
Public Deposited- Resource Type
- Creator
- Abstract
In this thesis, we study the problem of piercing pairwise intersecting disks in the plane. A set D of disks is said to be pierced by a point set P if each disk in D contains a point of P. Any set of pairwise intersecting unit disks can be pierced by 3 points, and any set of pairwise intersecting disks of arbitrary radius can be pierced by 4 points. However, existing algorithms for computing the piercing points all use the LP-type problem as a subroutine. We present a simple linear-time algorithm for finding 3 piercing points for pairwise intersecting unit disks and a simple linear-time algorithm for finding 5 piercing points for pairwise intersecting disks of arbitrary radius. Our algorithms use simple geometric transformation and avoid LP-type machinery. In this thesis, we also present a set of 9 pairwise intersecting unit disks that cannot be pierced by 2 points.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2021 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- 2021
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
wang-simplelineartimealgorithmsforpiercingpairwise.pdf | 2023-05-05 | Public | Download |