Introduction to Computational Geometry

Computational Geometry, WS 2007/08Lecture 1 – Part I

Prof. Dr. Thomas Ottmann

Algorithmen & Datenstrukturen, Institut für InformatikFakultät für Angewandte WissenschaftenAlbert-Ludwigs-Universität Freiburg

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 2

Overview

• Historicity– Proof-based geometry– Algorithmic geometry– Axiomatic geometry

• Computational geometry today• Problems and applications • Geometrical objects

– Points– Lines– Surfaces

• Analyses and techniques

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 3

Proof-Based Geometry

• Pythagoras’ Theorem:“The sum of the squares of the sides of a right triangle is equal to

the square of the hypotenuse”.

• Already known to the Babylonians and Egyptians as experimental fact.

• Pythagorean innovation: – A proof, independent of experimental

numerical verification

Pythagoras of Samos (582 BC to 507 BC)

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 4

Proof-Based Geometry

• Pythagoras’ Theorem:“The sum of the squares of the sides of a right triangle is equal to

the square of the hypotenuse”.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 5

Proof of Pythagoras’ Theorem

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 6

Algorithmic Geometry

• Ancient example (ca. 1900 BC - 1650 BC):

Problem 50: A circular field of diameter 9 has the same area as a square of side 8.

„Subtract 1/9 of the diameter which leaves 8 khet. The area is 8 multiplied by 8 or 64 setat“

Problem 48:Gives a hint of how this formula is constructed.

Rhind Mathematical Papyrus(Ancient Egypt, ca. 1850 BC)

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 7

Algorithmic Approach to Geometry

89

Problem: A circular field has diameter 9 khet. What is ist area?

Solution:Subtract 1/9-th of the diameter which leaves 8 khet. The area is 8 multiplied by 8, or 64 setat.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 8

Algorithmic Approach to Geometry

Trisect each side. Remove the cornertriangles. The resulting octogal figureapproximates the circle.

The area of the octagonal figure is:

9 9 – 4(1/2 3 3) = 63 82

The true area of the circle is: r2 .

Thus, (9/2)2 = 82 or

= 4 (8/9)2 = 3.160493827160…

Problem 48

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 9

Algorithmic Approach to Geometry

• Ancient method led to a very close approximate of the value PI (); up to 2% precision.

• Realises the “experimental quadrature of the circle”

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 10

Axiomatic Geometry

• Fundamental notions: – Points, straight lines, planes, incidence relation (“lies on”, “goes

through”)

• A1: For any two points P and Q, there is exactly one straight line g on which both P and Q lie.

• A2: For each straight line g, there is one point which is not on g.

Euclid of Alexandria(ca. 325 BC – 265 BC)

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 11

The Parallel Axiom

• A3: For each straight line g and each point P, which is not on g, there is exactly one straight line h, on which P lies and which does not have a common point with g.

Question: Is A3 independent of A1 and A2? Approach: Klein’s Model

ph2

h1

g

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 12

Computational Geometry Today

• Essential addition to our daily lives; a convenience taken for granted.

• Example: Global Positioning System (GPS)– Utilizes proof-based and algorithmic geometry

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 13

The Global Positioning System (GPS)

• A constellation of 28 satellites orbiting the earth– Inclination of 55° to the equator– 6 orbital planes at a height of 20,180km– Contains 4 atomic clocks on board each satellite– Signals takes 67.3ms to reach earth

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 14

The Geometry in GPS Technology

• The process of trilateration (similar to triangulation) with at least 3 satellites. Fourth satellite is used to synchronise time signals.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 15

Computational Geometry Today

• Applicative and valid in the Industrial world.

• Example: Paper folding (mass production: brochures, maps, newspapers, magazines, etc.)– Utilizes axiomatic geometry in an operational manner.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 16

Huzita’s Axioms

A1: Given two points p1 and p2, there is a unique fold that passes through both of them.

A2: Given two points p1 and p2, there is a unique fold that places p1 onto p2.

A3: Given two lines l1 and l2, there is a fold that places l1 onto l2.

A4: Given a point p1 and a line l1, there is a unique fold perpendicular to l1 that passes through point p1.

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 17

Huzita’s Axioms

A5: Given two points p1 and p2 and a line l1, there is a fold that places p1 onto l1 and passes through p2.

A6: Given two points p1 and p2 and two lines l1 and l2, there is a fold that places p1 onto l1 and p2 onto l2.

A7: Given one point p and two lines l1 and l2, there is a fold that places p onto l1 and perpendicular to l2.

Geometry based on these axioms is more powerful than the standard Compass-and-straightedge Geometry!

Computational Geometry, WS 2007/08Prof. Dr. Thomas Ottmann 18

Computational Geometry Today

• Back to the historical roots• Search for simple, robust, efficient algorithms• Fragmentation into:

– Rather theoretical investigations– Development of practically useful tools

• Contributions: Hundreds of research papers per year• Application of algorithmic techniques and data structures• Efficient solution of fundamental, “simple” problems• Development of new techniques and data structures

– Randomization and incremental construction– Competitive algorithms