Simple Linear Time Algorithms For Piercing Pairwise Intersecting Disks

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Wang, Yunkai

Date: 

2021

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: 

Computer Science
Mathematics

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Master of Computer Science: 
M.C.S.

Thesis Degree Level: 

Master's

Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).