### Archive

Archive for the ‘sage’ Category

## Computational Geometry in Python

To illustrate a few advantages of the scipy stack in one of my upcoming talks, I have placed an ipython notebook with (a reduced version of) the current draft of Chapter 6 (Computational Geometry) of my upcoming book: Mastering SciPy.

The raw ipynb can be downloaded from my github repository [blancosilva/Mastering-Scipy/], or viewed directly from the nbviewer at [this other link]

I also made a selection with some fun examples for the talk. You can download the presentation by clicking in the image above.

Enjoy!

## Searching (again!?) for the SS Central America

On Tuesday, September 8th 1857, the steamboat SS Central America left Havana at 9 AM for New York, carrying about 600 passengers and crew members. Inside of this vessel, there was stowed a very precious cargo: a set of manuscripts by John James Audubon, and three tons of gold bars and coins. The manuscripts documented an expedition through the yet uncharted southwestern United States and California, and contained 200 sketches and paintings of its wildlife. The gold, fruit of many years of prospecting and mining during the California Gold Rush, was meant to start anew the lives of many of the passengers aboard.

On the 9th, the vessel ran into a storm which developed into a hurricane. The steamboat endured four hard days at sea, and by Saturday morning the ship was doomed. The captain arranged to have women and children taken off to the brig Marine, which offered them assistance at about noon. In spite of the efforts of the remaining crew and passengers to save the ship, the inevitable happened at about 8 PM that same day. The wreck claimed the lives of 425 men, and carried the valuable cargo to the bottom of the sea.

It was not until late 1980s that technology allowed recovery of shipwrecks at deep sea. But no technology would be of any help without an accurate location of the site. In the following paragraphs we would like to illustrate the power of the scipy stack by performing a simple simulation, that ultimately creates a dataset of possible locations for the wreck of the SS Central America, and mines the data to attempt to pinpoint the most probable target.

We simulate several possible paths of the steamboat (say 10,000 randomly generated possibilities), between 7:00 AM on Saturday, and 13 hours later, at 8:00 pm on Sunday. At 7:00 AM on that Saturday the ship’s captain, William Herndon, took a celestial fix and verbally relayed the position to the schooner El Dorado. The fix was 31º25′ North, 77º10′ West. Because the ship was not operative at that point—no engine, no sails—, for the next thirteen hours its course was solely subjected to the effect of ocean current and winds. With enough information, it is possible to model the drift and leeway on different possible paths.

## Some results related to the Feuerbach Point

Given a triangle $\triangle ABC,$ the circle that goes through the midpoints of each side, $D, E, F,$ is called the Feuerbach circle. It has very surprising properties:

• It also goes through the feet of the heights, points $G, H, I.$
• If $Oc$ denotes the orthocenter of the triangle, then the Feuerbach circle also goes through the midpoints of the segments $OcA, OcB, OcC.$ For this reason, the Feuerbach circle is also called the nine-point circle.
• The center of the Feuerbach circle is the midpoint between the orthocenter and circumcenter of the triangle.
• The area of the circumcircle is precisely four times the area of the Feuerbach circle.

Most of these results are easily shown with sympy without the need to resort to Gröbner bases or Ritt-Wu techniques. As usual, we realize that the properties are independent of rotation, translation or dilation, and so we may assume that the vertices of the triangle are $A=(0,0), B=(1,0)$ and $C=(r,s)$ for some positive parameters $r,s>0.$ To prove the last statement, for instance we may issue the following:

>>> import sympy
>>> from sympy import *
>>> A=Point(0,0)
>>> B=Point(1,0)
>>> r,s=var('r,s')
>>> C=Point(r,s)
>>> D=Segment(A,B).midpoint
>>> E=Segment(B,C).midpoint
>>> F=Segment(A,C).midpoint
>>> simplify(Triangle(A,B,C).circumcircle.area/Triangle(D,E,F).circumcircle.area)
4


But probably the most amazing property of the nine-point circle, is the fact that it is tangent to the incircle of the triangle. With exception of the case of equilateral triangles, both circles intersect only at one point: the so-called Feuerbach point.

## An Automatic Geometric Proof

We are familiar with that result that states that, on any given triangle, the circumcenter, centroid and orthocenter are always collinear. I would like to illustrate how to use Gröbner bases theory to prove that the incenter also belongs in the previous line, provided the triangle is isosceles.

We start, as usual, indicating that this property is independent of shifts, rotations or dilations, and therefore we may assume that the isosceles triangle has one vertex at $A=(0,0)$, another vertex at $B=(1,0)$ and the third vertex at $C=(1/2, s)$ for some value $s \neq 0.$ In that case, we will need to work on the polynomial ring $R=\mathbb{R}[s,x_1,x_2,x_3,y_1,y_2,y_3,z],$ since we need the parameter $s$ free, the variables $x_1$ and $y_1$ are used to input the conditions for the circumcenter of the triangle, the variables $x_2$ and $y_2$ for centroid, and the variables $x_3$ and $y_3$ for the incenter (note that we do not need to use the orthocenter in this case).

We may obtain all six conditions by using sympy, as follows:

>>> import sympy
>>> from sympy import *
>>> A=Point(0,0)
>>> B=Point(1,0)
>>> s=symbols("s",real=True,positive=True)
>>> C=Point(1/2.,s)
>>> T=Triangle(A,B,C)
>>> T.circumcenter
Point(1/2, (4*s**2 - 1)/(8*s))
>>> T.centroid
Point(1/2, s/3)
>>> T.incenter
Point(1/2, s/(sqrt(4*s**2 + 1) + 1))


This translates into the following polynomials

$h_1=2x_1-1, h_2=8sy_1-4s^2+1$ (for circumcenter)
$h_3=2x_2-1, h_4=3y_2-s$ (for centroid)
$h_5=2x_3-1, h_6=(4sy_3+1)^2-4s^2-1$ (for incenter)

The hypothesis polynomial comes simply from asking whether the slope of the line through two of those centers is the same as the slope of the line through another choice of two centers; we could use then, for example, $g=(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1).$ It only remains to compute the Gröbner basis of the ideal $I=(h_1, \dotsc, h_6, 1-zg) \subset \mathbb{R}[s,x_1,x_2,x_3,y_1,y_2,y_3,z].$ Let us use SageMath for this task:

sage: R.<s,x1,x2,x3,y1,y2,y3,z>=PolynomialRing(QQ,8,order='lex')
sage: h=[2*x1-1,8*r*y1-4*r**2+1,2*x2-1,3*y2-r,2*x3-1,(4*r*y3+1)**2-4*r**2-1]
sage: g=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)
sage: I=R.ideal(1-z*g,*h)
sage: I.groebner_basis()
[1]


This proves the result.

## Sympy should suffice

I have just received a copy of Instant SymPy Starter, by Ronan Lamy—a no-nonsense guide to the main properties of SymPy, the Python library for symbolic mathematics. This short monograph packs everything you should need, with neat examples included, in about 50 pages. Well-worth its money.

To celebrate, I would like to pose a few coding challenges on the use of this library, based on a fun geometric puzzle from cut-the-knot: Rhombus in Circles

Segments $\overline{AB}$ and $\overline{CD}$ are equal. Lines $AB$ and $CD$ intersect at $M.$ Form four circumcircles: $(E)=(ACM), (F)=(ADM), (G)=(BDM), (H)=(BCM).$ Prove that the circumcenters $E, F, G, H$ form a rhombus, with $\angle EFG = \angle AMC.$

Note that if this construction works, it must do so independently of translations, rotations and dilations. We may then assume that $M$ is the origin, that the segments have length one, $A=(2,0), B=(1,0),$ and that for some parameters $a>0, \theta \in (0, \pi),$ it is $C=(a+1) (\cos \theta, \sin\theta), D=a (\cos\theta, \sin\theta).$ We let SymPy take care of the computation of circumcenters:

import sympy
from sympy import *

# Point definitions
M=Point(0,0)
A=Point(2,0)
B=Point(1,0)
a,theta=symbols('a,theta',real=True,positive=True)
C=Point((a+1)*cos(theta),(a+1)*sin(theta))
D=Point(a*cos(theta),a*sin(theta))

#Circumcenters
E=Triangle(A,C,M).circumcenter
F=Triangle(A,D,M).circumcenter
G=Triangle(B,D,M).circumcenter
H=Triangle(B,C,M).circumcenter


Finding that the alternate angles are equal in the quadrilateral $EFGH$ is pretty straightforward:

In [11]: P=Polygon(E,F,G,H)

In [12]: P.angles[E]==P.angles[G]
Out[12]: True

In [13]: P.angles[F]==P.angles[H]
Out[13]: True


To prove it a rhombus, the two sides that coincide on each angle must be equal. This presents us with the first challenge: Note for example that if we naively ask SymPy whether the triangle $\triangle EFG$ is equilateral, we get a False statement:

In [14]: Triangle(E,F,G).is_equilateral()
Out[14]: False

In [15]: F.distance(E)
Out[15]: Abs((a/2 - cos(theta))/sin(theta) - (a - 2*cos(theta) + 1)/(2*sin(theta)))

In [16]: F.distance(G)
Out[16]: sqrt(((a/2 - cos(theta))/sin(theta) - (a - cos(theta))/(2*sin(theta)))**2 + 1/4)


Part of the reason is that we have not indicated anywhere that the parameter theta is to be strictly bounded above by $\pi$ (we did indicate that it must be strictly positive). The other reason is that SymPy does not handle identities well, unless the expressions to be evaluated are perfectly simplified. For example, if we trust the routines of simplification of trigonometric expressions alone, we will not be able to resolve this problem with this technique:

In [17]: trigsimp(F.distance(E)-F.distance(G),deep=True)==0
Out[17]: False


Finding that $\angle EFG = \angle AMC$ with SymPy is not that easy either. This is the second challenge.

How would the reader resolve this situation?

Categories: Geometry, puzzles, sage, Teaching

## Edge detection: The Convolution Approach

Today I would like to show a very basic technique of detection based on simple convolution of an image with small kernels (masks). The purpose of these kernels is to enhance certain properties of the image at each pixel. What properties? Those that define what means to be an edge, in a differential calculus way—exactly as it was defined in the description of the Canny edge detector. The big idea is to assign to each pixel a numerical value that expresses its strength as an edge: positive if we suspect that such structure is present at that location, negative if not, and zero if the image is locally flat around that point. Masks can be designed so that they mimic the effect of differential operators, but these can be terribly complicated and give rise to large matrices.

The first approaches were performed with simple $3 \times 3$ kernels. For example, Faler came up with the following four simple masks that emulate differentiation:

$\begin{pmatrix} -1 & 0 & 1\\ -1 & 0 & 1\\ -1 & 0 & 1 \end{pmatrix}\quad \begin{pmatrix} 1 & 1 & 1\\ 0 & 0 & 0 \\ -1 & -1 & -1 \end{pmatrix}\quad \begin{pmatrix} -1 & -1 & -1 \\ -1 & 8 & -1 \\ -1 & -1 & -1 \end{pmatrix}\quad \begin{pmatrix} 0 & 1 & 0 \\ -1 & 0 & 1 \\ 0 & -1 & 0 \end{pmatrix}$

Note that, adding all the values of each matrix, one obtains zero. This is consistent with the third property required for our kernels: in the event of a locally flat area around a given pixel, convolution with any of these will offer a value of zero.

## Math Genealogy Project

I traced my mathematical lineage back into the XIV century at The Mathematics Genealogy Project. Imagine my surprise when I discovered that a big branch in the tree of my scientific ancestors is composed not by mathematicians, but by big names in the fields of Physics, Chemistry, Physiology and even Anatomy.

There is some “blue blood” in my family: Garrett Birkhoff, William Burnside (both algebrists). Archibald Hill, who shared the 1922 Nobel Prize in Medicine for his elucidation of the production of mechanical work in muscles. He is regarded, along with Hermann Helmholtz, as one of the founders of Biophysics.

Thomas Huxley (a.k.a. “Darwin’s Bulldog”, biologist and paleontologist) participated in that famous debate in 1860 with the Lord Bishop of Oxford, Samuel Wilberforce. This was a key moment in the wider acceptance of Charles Darwin’s Theory of Evolution.

There are some hard-core scientists in the XVIII century, like Joseph Barth and Georg Beer (the latter is notable for inventing the flap operation for cataracts, known today as Beer’s operation).

My namesake Franciscus Sylvius, another professor in Medicine, discovered the cleft in the brain now known as Sylvius’ fissure (circa 1637). One of his advisors, Jan Baptist van Helmont, is the founder of Pneumatic Chemistry and disciple of Paracelsus, the father of Toxicology (for some reason, the Mathematics Genealogy Project does not list any of these two in my lineage—I wonder why).

There are other big names among the branches of my scientific genealogy tree, but I will postpone this discovery towards the end of the post, for a nice punch-line.

Posters with your genealogy are available for purchase from the pages of the Mathematics Genealogy Project, but they are not very flexible neither in terms of layout nor design in general. A great option is, of course, doing it yourself. With the aid of python, GraphViz and a the sage library networkx, this becomes a straightforward task. Let me show you a naïve way to accomplish it:

Categories: sage