Hacker News new | more | comments | ask | show | jobs | submit login
Monge's theorem (wikipedia.org)
83 points by dimastopel 7 months ago | hide | past | web | favorite | 10 comments

Reminds me of flatland: There are three circular buildings. There's a line that all three people can be on such that each person thinks there are only two buildings and no one can agree on which two buildings are present.

Edit: Nope, nevermind, two of the points both see the medium and small circles!

However, it does seem like they all see only two buildings, though. Interesting point!

They all see at most two buildings. You can arrange the circles in a line so that each sees only one.

Is this the start of a new approach to public-key cryptography?

I strongly suspect that any cryptographically suitable problem derived from finding the intersection points of external tangent lines would reduce to the closest vector problem on lattices.

Okay so circles to the line is a one-way function. But how to encrypt/decrypt a message?

The wikipedia page has mostly geometric proofs. Are there algebraic proofs?

Let the circles be positioned at points p1, p2, p3 with radii r1, r2, r3 respectively. Note that we can get a family of circles with the same exterior tangents by simultaneously inter/extra-polating the position and radius of two other circles. Solving for a radius of 0 gives the following position for the intersection of those the tangents of circles 1 and 2.

    q3 = (r1 * p2 - r2 * p1) / (r1 - r2)
(with similar expression for q1 and q2). Using homogenous coordinates we get the following list for q1, q2, q3:

    ( r2 p3 - r3 p2 )  ( r3 p1 - r1 p3 )   ( r1 p2 - r2 p1 ) 
    (    r2 - r3    ), (    r3 - r1    ),  (    r1 - r2    )
now note that r1 q1 + r2 q2 + r3 q3 = 0, showing that they're not linearly independent and hence collinear.

A somewhat neater but more advanced proof, follows by making the positions pi also homogeneous and noting that (using Einstein summation notation):

    0 = ε_ijk rj rk
so we can determine the intersections to be

    qi = ε_ijk rj pk

    ri qi = ε_ijk ri rj pk = ε_jik rj ri pk = -ε_ijk ri rj pk = 0.

I studied it at the University, it was introduced after Pappo's theorem and other theorem demonstrated using Descriptive Feometry most of all.

On the other end it was a Projective Geometry course and at the end we used a lot the General Linear Group, in particular 4x4 matrices for bilinear forms, so it was like warming up with Geometry to arrive to the Algebra tools.

He's Pappus in English, for what it's worth.

Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact