The Origami Computational Model

Christian Lavoie McGill University Downtown Campus

    christian.lavoie@mail.mcgill.ca
      clavoie@christianlavoie.com

November 26, 2002

Abstract

The Origami Computational Model is a new abstract machine based on the ancient Japanese art of paper folding, and recent work on Mathematical and Computational Origami.

– Typeset by FoilTEX –

Christian Lavoie The Origami Computational Model

Administrative stuff

• Author: Christian Lavoie

• Subject: Origami Computational Model

• What you should know before this talk: – Euclid’s Edge & Compass

– Scheme and/or LISP

Christian Lavoie The Origami Computational Model

Structure of the talk

• History and Context

• The Origami Computation Model Definition (the OCM)

• OCM algorithms & lower bounds

• OCM contra other models of computation

• Applications – What’s the point?

• Future research – What’s next?

Christian Lavoie History and Context

Origami

• In Japan: No one seems to know exactly when it appeared, but most agree the Japanese were first

– oru means ”to fold”

– kami means ”paper”

• In Japan: Recreational use at the beginning of the 17th century, serious ceremonial use before that

• In Europe: Appeared around the 13th century (Spain)

• In England and the States: Appeared in the middle of the 20th century

Christian Lavoie History and Context

Mathematical Origami

• Burgeoning of a mathematical view in 1945, in the States

• The axioms of Origami – paper in 1992 ”Understanding Geometry through Origami Axioms” by Humiaki Huzita

• Formal definition of What can be done? using Origami, from a Mathematical point of view.

• Mainly a counterpoint to Euclid’s Edge & Compass

• Interesting results have recently started to come out of the community

– Topological results about face orientation

– Origami crease patterns are 2-colourable

Christian Lavoie History and Context

Computational Origami

• Algorithms, proofs, and the usual fruits.

• Few practical applications, but interesting ones:

– Map & solar sails folding

– Parachutes

– Crease patterns for raytracing – landscapes

• Defined as the study of folding, of crease patterns and algorithms related to either.

• Current state of the art:

– Universality results

– Efficient decision algorithms

– Computational intractability

Christian Lavoie The Origami Computational Model Definition

Design goals

• An original way to force teachers to accept flying paper airplanes!

• A machine that will use mathematical origami concepts as basic operations

• A machine that will let one use recent Computational Origami results to prove feasability results in the machine itself

• Did I mention a machine that is fun to work with?

Christian Lavoie The Origami Computational Model Definition

Implementation choices

• Bastard child of a LISP machine and a piece of paper

• Basically a computer model that uses:

– The axioms of origami to compute results and construct internal representations

– Some basic geometry queries to make decisions – LISP/Scheme list processing capabilities

Christian Lavoie The Origami Computational Model Definition

Internal representation

• Uses an internal Doubly Connected Edge List

• Uses the list primitives of LISP and Scheme Note this is not a complete computer! Missing are

• ways to represent code

• input/output facilities

• complete ’assembly language’ definition

Christian Lavoie The Origami Computational Model Definition

Some definitions

Point (Vertex) Euclid’s definition: A point is that which has no parts, or which has no magnitude. We will use the following A point is the minimal addressable unit of the OCM

Line A maximal set of point that the OCM considers to be colinear

Edge A continuous subset of a line

Face The intersection of the half-planes given by a set of lines and directions

Christian Lavoie The Origami Computational Model Definition

Queries & Data manipulation

• LISt Processing features

– car, cdr, append

– cons, list

• State queries

– Left/right turn (or colinearity) check on three points

– Left/right relative position of a point to a line – can ’intersect’

– Feasibility of various axioms of Origami

Christian Lavoie The Origami Computational Model Definition

Axioms of Origami

• As stated, mathematically defined operations on points and lines

• Quick list:

1. Folding through 2 points, or through a line

2. Folding a point on a point

3. Folding a line on a line

4. Folding a line on itself through a point

5. Folding a point on a line through a point

6. Folding 2 points on 2 different lines

Christian Lavoie The Origami Computational Model Definition

Axiom 1 – Folding through 2 points, or through a line

a = \frac{y_{2}−y_{1}}{x_{2}−x_{1}}

b = y_{1} − a ∗ x_{1}

Christian Lavoie The Origami Computational Model Definition

Axiom 2 – Folding a point on a point

a′ = −(\frac{y_{2}−y_{1}}{x_{2}−x_{1}})^{−1}

b′ = \frac{y_{2}−y_{1}}{2} − a′ ∗ \frac{x_{2}−x_{1}}{2}

Christian Lavoie The Origami Computational Model Definition

Axiom 3 – Folding a line on a line

Christian Lavoie The Origami Computational Model Definition

Axiom 4 – Folding a line on itself through a point

a′ = \frac{1}{−a}

b′ = y − a′ ∗ x

Christian Lavoie The Origami Computational Model Definition

Axiom 5 – Folding a point on a line through a point

Christian Lavoie The Origami Computational Model Definition

Axiom 5 – Folding a point on a line through a point

A couple of notes on axiom 5

• It’s mostly the direct equivalent of Edge & Compass’s Compass

• It allows one to solve 2nd degree equations, and thus build numbers which are powers of 2 x_{3} = \frac{2x_{2}−2ab+2y_{2}a+2SQRT}{2(1+a^{2})} y_{3} = \frac{a(2x_{2}−2ab+2y_{2}a+2SQRT)}{2(1+a^{2})} + b OR x_{3} = \frac{2x_{2}−2ab+2y_{2}a−2SQRT}{2(1+a^{2})} y_{3} = \frac{a(2x_{2}−2ab+2y_{2}a−2SQRT)}{2(1+a^{2})} + b Where SQRT is defined to be:

– Typeset by FoilTEX – 17 Christian Lavoie The Origami Computational Model Definition

SQRT = \sqrt{A + B + C + D} A = x_{2}^{2} − 2x_{2}ba + 2x_{2}y_{2}a + y_{2}^{2}a^{2} B = x_{1}^{2} − 2x_{1}x_{2} + y_{1}^{2} − 2y_{1}y_{2} C = −b^{2} + 2y_{2}b + x_{1}^{2}a^{2} − 2x_{1}x_{2}a^{2} D = y_{1}^{2}a^{2} − 2y_{1}y_{2}a^{2}

Christian Lavoie The Origami Computational Model Definition

Axiom 6 – Folding 2 points on 2 different lines

Christian Lavoie The Origami Computational Model Definition

Axiom 6 – Folding 2 points on 2 different lines

A couple of notes on axiom 6

• It allows one to solve 3rd degree equations, and thus build numbers which are powers of 3

• This one is the interesting one... it’s impossible in Edge & Compass!

y1^{′} = a_{1}x1^{′} + b_{1}

y2^{′} = a_{2}x2^{′} + b_{2}

\frac{y_{1}−y′_{1}}{x_{1}−x′_{1}} = \frac{y_{2}−y′_{2}}{x_{2}−x′_{2}}

(x_{1} − x_{2})^{2} + (y_{1} − y_{2})^{2} = (x1^{′} − x2^{′})^{2} + (y1^{′} − y2^{′})^{2}

Christian Lavoie The Origami Computational Model Definition

Axiom 6 – solution

Which solves to

x1^{′} = \frac{−a_{2}+x1−b_{1}+b_{2}−y_{2}+y_{1}+x_{2}a_{2}}{−a_{1}+a_{2}}

y1^{′} = \frac{−a_{2}a_{1}x_{1}+a_{1}b_{2}+a_{1}y_{2}+a_{1}y_{1}+a_{2}x_{2}a_{1}−a_{2}b_{1}}{−a_{1}+a_{2}}

x2^{′} = \frac{−b_{1}+b_{2}+y_{1}−y_{2}+a_{1}x_{1}+x_{2}+a_{1}}{−a_{1}+a_{2}}

y2^{′} = \frac{−a_{2}b_{1}+a_{2}y_{1}+a_{2}y_{2}−a_{2}a_{1}x_{1}+a_{2}x_{2}a_{1}+a_{1}b_{2}}{−a_{1}+a_{2}}

– Typeset by FoilTEX – 21

Christian Lavoie OCM Algorithms & lower bounds

And now the fun stuff: What can we do with it?

• Convex hulls – Jarvis’ March

– Graham’s Scan?

• Voronoi Diagrams – Hard!

• Linear Programming – Two dimensional linear programming in O(N)

Christian Lavoie OCM Algorithms & lower bounds

Jarvis’ March

(define jarvis-march-internal
  (lambda (stop-point first-point second-point)
    (let ((next-point (jarvis-next first-point second-point)))
      (if (= next-point stop-point)
        next-point
        (cons next-point
(jarvis-march-internal stop-point second-point next-point))))))
(define jarvis-march
  (lambda (points-cloud)
    (let ((first-point (find-lowest-y points-cloud))
          (second-point (jarvis-next lower-right-corner first-point)))
        (cons first-point
(jarvis-march-internal first-point first-point second-point)))))

Christian Lavoie OCM Algorithms & lower bounds

Graham’s scan

• Possible, but we need to figure out how to sort • Sorting on linked lists: merge sort, or O(N^{2}) sorts • Then use the 3 coins-algorithm as is

• Without explicit stacks, surprisingly hard

Christian Lavoie OCM Algorithms & lower bounds

Linear Programming & Voronoi Diagrams

Linear programming:

• Class algorithm works as is!

• But blows up badly Voronoi Diagrams:

• Class algorithm works as is!

• But blows up

Christian Lavoie OCM Algorithms & lower bounds

Comments on generic techniques

Randomization No change, but need to code a new pseudo random number generator

Linesweep Works perfectly, remember we can sort on x or y coordinates

Duality Hard to represent as is, as the model is often clutered with random lines, but most certainly feasible

Linear Programming Feasible, as we saw, but most advanced algorithms start to clutch at straws when brought into the OCM

Parallelization Very hard to create a working OCM model for parallel algorithms: folds almost always intersect, and thus very few query we make are unnaffected by the other ’threads’

Christian Lavoie OCM contra other systems & other models of computation

Origami contra Edge & Compass

• Origami is better!

• Edge & Compasscan do almost all the axioms of Origami: it cannot do Axiom 6: Two lines on two points

• Origami can trisect an angle!

• Origami still cannot square the circle

Christian Lavoie OCM contra other systems & other models of computation

Technical digression: Angle trisecting

Christian Lavoie OCM contra other systems & other models of computation

Origami contra Turing Machines & RAM Models

• OCM is not a Turing Machine

– No notion of tape – data enters the OCM magically

– Number of state is infinite

• But is the OCM Turing Complete?

• OCM is not remotely a superset of the RAM Model

• OCM doesn’t have arithmetic capabilities

• OCM doesn’t have pointers & other bitrepresentations

• For example, OCM cannot do hashing (no O(1) floor function)!

Christian Lavoie OCM contra other systems & other models of computation

– Could always use segment intersection and judiciously placed test segments, but this is O(N) in memory, and O(N) in time for setup

– And we need trigonometry to calculate the segments’ positions right, which the OCM won’t do for us

• Origami is asymptotically faster than current implementations of the RAM model in some cases though:

– The OCM can create O(N) lists in O(1)

– The OCM doesn’t need O(bit − size) algorithms for calculating the folds’ slopes

Christian Lavoie OCM contra other systems & other models of computation

Thus...

• Origami is better than Edge & Compass, but not necessarily a superset

• OCM is very much an Algebraic Decision Tree

• Turing Machines and RAM Models are better at most things, but the OCM has an infinite parallel DCEL evaluation engine

Christian Lavoie Applications – What’s the point?

What’s the point?

• Very abstract machine, few direct practical applications

• But Computational Models study is very important!

– Jeff Erickson has proven that in his model, based on Edge & Compass, P != NP

– Other models are is use out there, for the same reasons other geometries are out there: Problem context

Christian Lavoie Future research – What’s next?

What’s next?

• Applications: Topology

• Extensions: The Third Dimension & Fold angles • Applications: Raytracing

Christian Lavoie Future research – What’s next?

Building a real one

Quite a couple of problems:

• The ’infinite parallel DCEL engine’ is impossible, but we can simply invent a new algorithm measurement

• Colinearity happens all the time – infinite precision numerics don’t exist