Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Covering a Triangle with Disks Centered on its Boundary

Covering a Triangle with Disks Centered on its Boundary

File(s)
91-1242.ps (246.79 KB)
91-1242.pdf (692.48 KB)
Permanent Link(s)
https://hdl.handle.net/1813/7082
Collections
Computer Science Technical Reports
Author
Connelly, Robert
Freimer, Robert
Abstract

Let $\cal P$ be a triangle and $\cal D_{1}, \cal D_{2}$ be disks centered on the boundary of $\cal P$ with radii $r_{1}$, $r}{2}$. The disks are chosen so that $\cal D{1}$ $\cup$ $\cal D$${2}$ covers $\cal P$ and $r{1}$ + $r_{2}$ is minimized. We show that an optimal covering must exist with $r_{2}$ = 0. In such a single disk covering, $\cal D_{1}$ is always located on the longest side of $\cal P$. The exact location and and size depend on the angles of $\cal P$; we provide a complete characterization and then generalize it to convex polygons. We show that the minimum covering disk can be determined in $\cal O (n)$ time for a convex polygon with $n$ sides. However, it is open for $n \geq$ 4 whether there is always a single disk covering that is optimal.

Date Issued
1991-11
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1242
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance