Computer Science – Computational Geometry
Scientific paper
2011-09-08
Computer Science
Computational Geometry
Full version of the Graph Drawing 2011 conference version, 16 pages, 9 figures
Scientific paper
We study the problem of arranging a set of $n$ disks with prescribed radii on $n$ rays emanating from the origin such that two neighboring rays are separated by an angle of $2\pi/n$. The center of the disks have to lie on the rays, and no two disk centers are allowed to lie on the same ray. We require that the disks have disjoint interiors, and that for every ray the segment between the origin and the boundary of its associated disk avoids the interior of the disks. Let $\r$ be the sum of the disk radii. We introduce a greedy strategy that constructs such a disk arrangement that can be covered with a disk centered at the origin whose radius is at most $2\r$, which is best possible. The greedy strategy needs O(n) arithmetic operations. As an application of our result we present an algorithm for embedding unordered trees with straight lines and perfect angular resolution such that it can be covered with a disk of radius $n^{3.0367}$, while having no edge of length smaller than 1. The tree drawing algorithm is an enhancement of a recent result by Duncan et al. [Symp. of Graph Drawing, 2010] that exploits the heavy-edge tree decomposition technique to construct a drawing of the tree that can be covered with a disk of radius $2 n^4$.
Halupczok Immanuel
Schulz André
No associations
LandOfFree
Pinning Balloons with Perfect Angles and Optimal Area does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Pinning Balloons with Perfect Angles and Optimal Area, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pinning Balloons with Perfect Angles and Optimal Area will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-475151