4-Local Search gives a 4-approximation algorithm to the Geometric Hitting Set Problem

Imagine you are the head of the education department of a metropole like São Paulo, the biggest city in Brazil. The mayor commended a survey to evaluate how well the schools were distributed around the town. Not that well, sadly. There exist some empty terrains and the mayor wants to use this space to build new schools, but he is not sure of how many to build neither where the best locations are. Your task is to assign the construction sites of the new schools.

The schools should be positioned following two criteria:

  1. Every student must spend at most 30 minutes from home to the school.
  2. Every school should be close enough from security safe facilities, in the case of an emergency.

Based on these, your team created a map covering the city with disks of different radii. Each disk is centered at a security safe facility, and a person can move from any two points inside each disk in less than 30 minutes. Your task is now reduced to find the minimum number of construction sites such that each disk has at least one school on it. This problem is also known as the minimum hit-set problem. The mayor was impressed with your solution and started to say your name for the press.

Continue reading

The Brachistochrone Curve

Let B to be a ball positioned at some point A. Considering that only the gravitational force acts on the ball, what is the trajectory the ball should follow in order to reach a point C in the shortest time? The solution of this problem is known as the brachistochrone curve.

Although similar, the brachistochrone curve has a different description than the tautochrone curve. The amusing fact is that they are, indeed, the same. The brilliant argument exposed next is due to Johann Bernoulli.

The principle of least time

Light has different speeds at different mediums. That’s why we perceive the phenomenon of refraction when observing objects underwater while ourselves stand out of it. Willebrord Snellius was the first to give a relation between the speed of light in different mediums and its angle of refraction. By denoting n_1 and n_2 constants related with the speed of light at mediums M_1 and M_2 (also called refraction indexes of mediums M_1 and M_2); the entry ray’s angle with the plane P separating M_1 and M_2 by \theta_1; and \theta_2 the out ray’s angle, the relation is written as:

\displaystyle \frac{n_1}{n_2} = \frac{ \sin \theta_1 }{\sin \theta_2}

Continue reading

The Tautochrone Curve

The tautochrone is the curve in which a ball, positioned anywhere on the curve, will take the same time to arrive at its lowest point.

tautochrone_curve
Source: Wikipedia

In a physical model where uniform gravity is the only force acting on the ball, the tautochrone curve is a cycloid (the curve described by a fixed point in a rolling circle), as correctly proven by Huygens in 1673 [BOYDE] using pure geometric arguments. We are going to present two different ways to arrive at this result.

Continue reading

The Laplace Transform

The expression “It is easy to see that…” was used many and many times by the scientist Pierre-Simon Laplace when he didn’t want to come into the details of its ideas. One of the main contributions of Laplace, the Laplace Transform, will be explained here, hopefully in an easy to see fashion.

Definition

Let f:\mathcal{R}\rightarrow\mathcal{R}. Its Laplace transform is defined as:

\displaystyle \mathcal{L}\{f(t)\} = F(s) = \int_{0}^{\infty}{e^{-st}f(t)dt}.

If f is piecewise continuous and there exist real positive numbers a,K,M such that |f(t)| \leq Ke^{at} \quad \forall t \geq M, then the integral above is well defined for all values s > a.

Continue reading

The Catenary Curve – On the way to the Calculus of Variations

In the beginning of the last decade of the 17th century, Jacob Bernoulli proposed the problem of the catenary; in 1696, Johann Bernoulli proposed the problem of the brachistochrone; some years later, Daniel Bernoulli would suggest to Euler the right functional to solve the elastica problem. The Bernoulli’s family had a great influence in the development of the Calculus of Variations, which was formalized by Euler in his book of 1744. Here the catenary problem and its solution are described in detail.

Definition and first model.

In 1690, Jacob Bernoulli stated the following problem:

Assume you have a perfectly elastic wire (it can be deformed by the action of some force, but its shape is recovered immediately after the forces are ceased) made of a material with uniform density \lambda.  The two extremities of the wire are attached at the top of two columns of the same height. Moreover, assume that the only forces acting on the wire are tension and gravity. What is the equation described by the wire?

Continue reading