Skip to main content
union of their areas -> area of their union
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

I like the following problem:

Let $S$ be a finite collection of circles in the plane such that the unionarea of their areasunion is $1$. Show that you can pick disjoint circles whose area is at least $1/9$.

The solution idea is to do a greedy selection: First pick the circle of maximum radius. Then take away any of the other circles that are contained in three times this radius and repeat.

This greedy idea is a bit 'algorithmic' and the many similar variants are used for a wide variety of approximation algorithms.

I like the following problem:

Let $S$ be a finite collection of circles in the plane such that the union of their areas is $1$. Show that you can pick disjoint circles whose area is at least $1/9$.

The solution idea is to do a greedy selection: First pick the circle of maximum radius. Then take away any of the other circles that are contained in three times this radius and repeat.

This greedy idea is a bit 'algorithmic' and the many similar variants are used for a wide variety of approximation algorithms.

I like the following problem:

Let $S$ be a finite collection of circles in the plane such that the area of their union is $1$. Show that you can pick disjoint circles whose area is at least $1/9$.

The solution idea is to do a greedy selection: First pick the circle of maximum radius. Then take away any of the other circles that are contained in three times this radius and repeat.

This greedy idea is a bit 'algorithmic' and the many similar variants are used for a wide variety of approximation algorithms.

Source Link

I like the following problem:

Let $S$ be a finite collection of circles in the plane such that the union of their areas is $1$. Show that you can pick disjoint circles whose area is at least $1/9$.

The solution idea is to do a greedy selection: First pick the circle of maximum radius. Then take away any of the other circles that are contained in three times this radius and repeat.

This greedy idea is a bit 'algorithmic' and the many similar variants are used for a wide variety of approximation algorithms.

Post Made Community Wiki by Sandeep Silwal