Geometry Constructions: A Synthesis of Theory and Practice

 
Synthesizing Geometry Constructions
Sumit Gulwani
MSR, Redmond
Vijay Korthikanti
UIUC
Ashish Tiwari
SRI
Given a 
triangle XYZ
,
construct 
circle C
 such that
C passes through X, Y, and Z.
1
 
Ruler/Compass based Geometry Constructions
X
Z
Y
 
L1
 
L2
 
N
 
C
Good platform for teaching logical reasoning.
Visual Nature:
Makes it more accessible.
Exercises both logical/visual abilities of left/right brain.
Fun Aspect:
Ruler/compass restrictions make it fun, as in sports.
Application in dynamic geometry or animations.
“Constructive” geometry macros (unlike numerical
methods) enable fast re-computation of derived objects
from free (moving) objects.
2
Why Geometry Constructions?
Problem Formulation (as Program Synthesis)
Synthesis Algorithm (based on inter-disciplinary ideas)
Idea 1: from Theory
Idea 2: from PL
Idea 3: from AI
Experiments
Future Vision
3
Outline
Types:
 Point, Line, Circle
Methods:
Ruler(Point, Point) -> Line
Compass(Point, Point) -> Circle
Intersect(Circle, Circle) -> Pair of Points
Intersect(Line, Circle) -> Pair of Points
Intersect(Line, Line) -> Point
Geometry Program: 
A straight-line composition of
the above methods.
4
Programming Language for Geometry Constructions
Given a 
triangle XYZ
, construct 
circle C
 such that C
passes through X, Y, and Z.
5
Example Problem: Program
 
 
 
1.
C1 = Compass(X,Y);
2.
C2 = Compass(Y,X);
3.
<P1,P2> = Intersect(C1,C2);
4.
L1 = Ruler(P1,P2);
5.
D1 = Compass(Z,X);
6.
D2 = Compass(X,Z);
7.
<R1,R2> = Intersect(D1,D2);
8.
L2 = Ruler(R1,R2);
9.
N = Intersect(L1,L2);
10.
C = Compass(N,X);
X
Z
Y
 
C1
 
C2
 
P1
 
P2
 
L1
 
D2
 
D1
 
R1
 
R2
 
L2
 
N
 
C
Conjunction of predicates over arithmetic expressions
Predicates
    p   :=   
e
1
 = 
e
2
    
  
       |   
e
1
 
 
e
2
    
 
                 |   
e
1
 
·
 
e
2
Arithmetic Expressions
     e   :=  Distance(Point, Point)
    
    
        |  Slope(Point, Point)
                                                |  
e
1
 
§
 
e
2
    
        |  c
6
Specification Language for Geometry Programs
 
Given a 
triangle XYZ
, construct 
circle C
 such that C
passes through X, Y, and Z.
 
Precondition:
Slope(X,Y) 
 Slope(X,Z)  
Æ
 Slope(X,Y) 
 Slope(Z,X)
 
Postcondition:
LiesOn(X,C) 
Æ
 LiesOn(Y,C) 
Æ 
LiesOn(Z,C)
 
Where LiesOn(X,C) 
´
                Distance(X,Center(C)) = Radius(C)
 
 
 
 
Example Problem: Precondition/Postcondition
 
7
 
Let P be a geometry program that computes
outputs O from inputs I.
 
Verification Problem:
 Check the validity of the
following Hoare triple.
  
Assume Pre(I);
         
  
           P
  
Assert Post(I,O);
 
Synthesis Problem:
 Given Pre(I), Post(I,O), find P
such that the above Hoare triple is valid.
8
Verification/Synthesis Problem for Geometry Programs
Problem Formulation (as Program Synthesis)
Synthesis Algorithm (based on inter-disciplinary ideas)
Idea 1: from Theory
Idea 2: from PL
Idea 3: from AI
Experiments
Future Vision
9
Outline
 
Pre(I), P, Post(I,O)
 
a)
Existing decision procedures are complex.
 
b)
New efficient approach: Random Testing!
1.
Choose I’ randomly from the set { I | Pre(I) }.
2.
Compute O’ := P(I’).
3.
If O’ satisfies Post(I’,O’) output “Verified”.
 
Correctness Proof of (b):
Objects constructed by P can be described using
polynomial ops (+,-,*), square-root & division operator.
The randomized polynomial identity testing algorithm
lifts to square-root and division operators as well !
10
Approaches to Verification Problem
 
Synthesis Algorithm:
// First obtain a random input-output example.
1.
Choose I’ randomly from the set { I | Pre(I) }.
2.
Compute O’ s.t. Post(I’,O’) using numerical methods.
// Now obtain a construction that can generate O’ from I’
(using exhaustive search).
3.
S := I’;
4.
While (S does not contain O’)
5.
         S := S 
[
 { 
M(O
1
,
O
2
) | 
O
i
 
2
 S, M 
2
 Methods }
6.
Output construction steps for O’.
11
Idea 1 (from Theory): Symbolic Reasoning -> Concrete
Given a 
triangle XYZ
, construct 
circle C
 such that C
passes through X, Y, and Z.
12
Error Probability of the algorithm is extremely low.
 
L1 = Ruler(P1,P2);
L2 = Ruler(R1,R2);
N = Intersect(L1,L2);
C = Compass(N,X);
12
 
For an equilateral 
4
XYZ, incenter
coincides with circumcenter N.
But what are the chances of choosing a
random 
4
XYZ to be an equilateral one?
X
Z
Y
L1
L2
N
C
Synthesis algorithm times out because programs are large.
Identify a library of commonly used patterns (pattern =
“sequence of geometry methods”)
E.g., 
perpendicular/angular bisector, midpoint, tangent, etc.
  
S := S 
[
 { M(O
1
,O
2
) | O
i
 
2
 S, M 
2
 Methods }
  
S := S 
[
 { M(O
1
,O
2
) | O
i
 
2
 S, M 
2
 LibMethods }
Two key advantages:
Search space: large depth -> small depth
Easier to explain solutions to students.
13
Idea 2 (from PL): High-level Abstractions
Given a 
triangle XYZ
, construct 
circle C
 such that C
passes through X, Y, and Z.
14
Use of high-level abstractions reduces program size
 
1.
C1 = Compass(X,Y);
2.
C2 = Compass(Y,X);
3.
<P1,P2> = Intersect(C1,C2);
4.
L1 = Ruler(P1,P2);
5.
D1 = Compass(Z,X);
6.
D2 = Compass(X,Z);
7.
<R1,R2> = Intersect(D1,D2);
8.
L2 = Ruler(R1,R2);
9.
N = Intersect(L1,L2);
10.
C = Compass(N,X);
 
 
1.
L1 = PBisector(X,Y);
2.
L2 = PBisector(X,Z);
3.
N = Intersect(L1,L2);
4.
C = Compass(N,X);
Synthesis algorithm is inefficient because the search space
is too wide and hence still huge.
Prune forward search by using A* style heuristics.
      
S := S 
[
 { M(O
1
,O
2
) | O
i
 
2
 S, M 
2
 LibMethods } 
S := S 
[
 {M(O
1
,O
2
) | O
i
2
S, M
2
LibMethods, 
IsGood(M(O
1
,O
2
)) }
Example: If a method constructs a line L that passes
through a desired output point, then L is “good” (i.e.,
worth constructing).
15
Idea 3 (from AI): Goal Directed Search
Given a 
triangle XYZ
,
construct 
circle C
 such that
C passes through X, Y, and Z.
16
Effectiveness of Goal-directed search
 
16
 
L1 and L2 are immediately constructed since
they pass through output point N.
On the other hand, other lines like angular
bisectors are not eagerly constructed.
X
Z
Y
L1
L2
N
C
Problem Formulation (as Program Synthesis)
Synthesis Algorithm (based on inter-disciplinary ideas)
Idea 1: from Theory
Idea 2: from PL
Idea 3: from AI
Experiments
Future Vision
17
Outline
 
25 benchmark problems.
 
such as: 
Construct a square whose extended sides
pass through 4 given points.
 
18 problems less than 1 second.
    4 problems between 1-3 seconds.
    3 problems 13-82 seconds.
 
Idea 2 (high-level abstractions) reduces programs
of size 3-45 to 3-13.
 
Idea 3 (goal-directedness) improves performance
by factor of 10-1000 times on most problems.
18
Experimental Results
19
Search space Exploration: With/without goal-directness
Problem Formulation (as Program Synthesis)
Synthesis Algorithm (based on inter-disciplinary ideas)
Idea 1: from Theory
Idea 2: from PL
Idea 3: from AI
Experiments
Future Vision
20
Outline
21
Problem Solving Engine with Natural Interfaces
Natural Language Processing/
Sketch Recognition
Paraphrasing
Program Synthesis Engine
 
Problem Description 
in
 
English/Ink
Problem Description 
as
 
Logical Relation
Solution 
as
 
Straight-line Program
 
Solution
 in 
English
 
Joint work: Umair Ahmed, Kalika Bali, Monojit Chaudhuri (MSR India)
                   Salman Cheema, Joseph LaViola (Univ of Central Florida)
Construct a triangle ABC with AB = 7 cm, angle B =
60 degree and BC + CA = 10 cm.
22
GeoSynth Demo
23
Various Aspects of an Intelligent Tutoring System
Goal: Make Education Interactive and Fun.
Dimensions in Program Synthesis (PPDP 2010)
Intent
: Logic or Natural language/Ink
Language
: Geometry programs
Search
: Exhaustive search made efficient by property testing,
high-level abstractions, goal-directedness.
Who benefits? 
Students/Teachers
What is the value addition? 
Towards making education
interactive, fun,  and accessible anytime/anywhere.
Education is a new important application area for PL.
Motivation:
 Classroom size and costs rising, repetitive tasks.
Technology Trends:
 new devices, social networking.
PL has central role
: 100 researchers may be busy for 20 years.
If you share this vision too, please get in touch!
24
Conclusion
Slide Note
Embed
Share

Explore the world of geometry constructions through ruler/compass-based techniques, combining logical reasoning and visual elements to create engaging exercises. Discover the programming language for constructing geometric shapes, with an example problem and a specification language for geometry programs.

  • Geometry Constructions
  • Ruler Compass
  • Programming Language
  • Logical Reasoning
  • Visual Elements

Uploaded on Sep 21, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Synthesizing Geometry Constructions Sumit Gulwani MSR, Redmond Vijay Korthikanti UIUC Ashish Tiwari SRI

  2. Ruler/Compass based Geometry Constructions Given a triangle XYZ, construct circle C such that C passes through X, Y, and Z. C L1 L2 N Z X Y 1

  3. Why Geometry Constructions? Good platform for teaching logical reasoning. Visual Nature: Makes it more accessible. Exercises both logical/visual abilities of left/right brain. Fun Aspect: Ruler/compass restrictions make it fun, as in sports. Application in dynamic geometry or animations. Constructive geometry macros (unlike numerical methods) enable fast re-computation of derived objects from free (moving) objects. 2

  4. Outline Problem Formulation (as Program Synthesis) Synthesis Algorithm (based on inter-disciplinary ideas) Idea 1: from Theory Idea 2: from PL Idea 3: from AI Experiments Future Vision 3

  5. Programming Language for Geometry Constructions Types: Point, Line, Circle Methods: Ruler(Point, Point) -> Line Compass(Point, Point) -> Circle Intersect(Circle, Circle) -> Pair of Points Intersect(Line, Circle) -> Pair of Points Intersect(Line, Line) -> Point Geometry Program: A straight-line composition of the above methods. 4

  6. Example Problem: Program Given a triangle XYZ, construct circle C such that C passes through X, Y, and Z. 1. C1 = Compass(X,Y); 2. C2 = Compass(Y,X); 3. <P1,P2> = Intersect(C1,C2); 4. L1 = Ruler(P1,P2); 5. D1 = Compass(Z,X); 6. D2 = Compass(X,Z); 7. <R1,R2> = Intersect(D1,D2); 8. L2 = Ruler(R1,R2); 9. N = Intersect(L1,L2); 10.C = Compass(N,X); C L1 L2 N C1 C2 P1 R1 D1 Z X Y R2 D2 P2 5

  7. Specification Language for Geometry Programs Conjunction of predicates over arithmetic expressions Predicates p := e1 = e2 | e1 e2 | e1 e2 Arithmetic Expressions e := Distance(Point, Point) | Slope(Point, Point) | c | e1 e2 6

  8. Example Problem: Precondition/Postcondition Given a triangle XYZ, construct circle C such that C passes through X, Y, and Z. Precondition: Slope(X,Y) Slope(X,Z) Slope(X,Y) Slope(Z,X) Postcondition: LiesOn(X,C) LiesOn(Y,C) LiesOn(Z,C) Where LiesOn(X,C) Distance(X,Center(C)) = Radius(C) 7

  9. Verification/Synthesis Problem for Geometry Programs Let P be a geometry program that computes outputs O from inputs I. Verification Problem: Check the validity of the following Hoare triple. Assume Pre(I); P Assert Post(I,O); Synthesis Problem: Given Pre(I), Post(I,O), find P such that the above Hoare triple is valid. 8

  10. Outline Problem Formulation (as Program Synthesis) Synthesis Algorithm (based on inter-disciplinary ideas) Idea 1: from Theory Idea 2: from PL Idea 3: from AI Experiments Future Vision 9

  11. Approaches to Verification Problem Pre(I), P, Post(I,O) a) Existing decision procedures are complex. b) New efficient approach: Random Testing! 1. Choose I randomly from the set { I | Pre(I) }. 2. Compute O := P(I ). 3. If O satisfies Post(I ,O ) output Verified . Correctness Proof of (b): Objects constructed by P can be described using polynomial ops (+,-,*), square-root & division operator. The randomized polynomial identity testing algorithm lifts to square-root and division operators as well ! 10

  12. Idea 1 (from Theory): Symbolic Reasoning -> Concrete Synthesis Algorithm: // First obtain a random input-output example. 1. Choose I randomly from the set { I | Pre(I) }. 2. Compute O s.t. Post(I ,O ) using numerical methods. // Now obtain a construction that can generate O from I (using exhaustive search). 3. S := I ; 4. While (S does not contain O ) 5. S := S [ { M(O1,O2) | Oi2 S, M 2 Methods } 6. Output construction steps for O . 11

  13. Error Probability of the algorithm is extremely low. Given a triangle XYZ, construct circle C such that C passes through X, Y, and Z. L1 = Ruler(P1,P2); L2 = Ruler(R1,R2); N = Intersect(L1,L2); C = Compass(N,X); C L1 L2 N Z X Y For an equilateral 4XYZ, incenter coincides with circumcenter N. But what are the chances of choosing a random 4XYZ to be an equilateral one? 12 12

  14. Idea 2 (from PL): High-level Abstractions Synthesis algorithm times out because programs are large. Identify a library of commonly used patterns (pattern = sequence of geometry methods ) E.g., perpendicular/angular bisector, midpoint, tangent, etc. S := S [ { M(O1,O2) | Oi2 S, M 2 Methods } S := S [ { M(O1,O2) | Oi2 S, M 2 LibMethods } Two key advantages: Search space: large depth -> small depth Easier to explain solutions to students. 13

  15. Use of high-level abstractions reduces program size Given a triangle XYZ, construct circle C such that C passes through X, Y, and Z. 1. C1 = Compass(X,Y); 2. C2 = Compass(Y,X); 3. <P1,P2> = Intersect(C1,C2); 4. L1 = Ruler(P1,P2); 5. D1 = Compass(Z,X); 6. D2 = Compass(X,Z); 7. <R1,R2> = Intersect(D1,D2); 8. L2 = Ruler(R1,R2); 9. N = Intersect(L1,L2); 10.C = Compass(N,X); 1. L1 = PBisector(X,Y); 2. L2 = PBisector(X,Z); 3. N = Intersect(L1,L2); 4. C = Compass(N,X); 14

  16. Idea 3 (from AI): Goal Directed Search Synthesis algorithm is inefficient because the search space is too wide and hence still huge. Prune forward search by using A* style heuristics. S := S [ { M(O1,O2) | Oi2 S, M 2 LibMethods } S := S [ {M(O1,O2) | Oi2S, M2LibMethods, IsGood(M(O1,O2)) } Example: If a method constructs a line L that passes through a desired output point, then L is good (i.e., worth constructing). 15

  17. Effectiveness of Goal-directed search Given a triangle XYZ, construct circle C such that C passes through X, Y, and Z. C L1 L2 N Z X Y L1 and L2 are immediately constructed since they pass through output point N. On the other hand, other lines like angular bisectors are not eagerly constructed. 16 16

  18. Outline Problem Formulation (as Program Synthesis) Synthesis Algorithm (based on inter-disciplinary ideas) Idea 1: from Theory Idea 2: from PL Idea 3: from AI Experiments Future Vision 17

  19. Experimental Results 25 benchmark problems. such as: Construct a square whose extended sides pass through 4 given points. 18 problems less than 1 second. 4 problems between 1-3 seconds. 3 problems 13-82 seconds. Idea 2 (high-level abstractions) reduces programs of size 3-45 to 3-13. Idea 3 (goal-directedness) improves performance by factor of 10-1000 times on most problems. 18

  20. Search space Exploration: With/without goal-directness 19

  21. Outline Problem Formulation (as Program Synthesis) Synthesis Algorithm (based on inter-disciplinary ideas) Idea 1: from Theory Idea 2: from PL Idea 3: from AI Experiments Future Vision 20

  22. Problem Solving Engine with Natural Interfaces Problem Description in English/Ink Natural Language Processing/ Sketch Recognition Problem Description as Logical Relation Program Synthesis Engine Solution as Straight-line Program Paraphrasing Solution in English Joint work: Umair Ahmed, Kalika Bali, Monojit Chaudhuri (MSR India) Salman Cheema, Joseph LaViola (Univ of Central Florida) 21

  23. GeoSynth Demo Construct a triangle ABC with AB = 7 cm, angle B = 60 degree and BC + CA = 10 cm. 22

  24. Various Aspects of an Intelligent Tutoring System Goal: Make Education Interactive and Fun. Education Studio PL Connection Education Studio Automated Solving Automated Solving Hint Generation Automated Grading Pointing Mistakes Suggesting Fixes Problem Generation Content Creation PL Connection Program Synthesis Program Synthesis Interpolants Program Verification Bug Isolation Program Repair Test Input Generation Visual Studio Intellisense 23

  25. Conclusion Dimensions in Program Synthesis (PPDP 2010) Intent: Logic or Natural language/Ink Language: Geometry programs Search: Exhaustive search made efficient by property testing, high-level abstractions, goal-directedness. Who benefits? Students/Teachers What is the value addition? Towards making education interactive, fun, and accessible anytime/anywhere. Education is a new important application area for PL. Motivation: Classroom size and costs rising, repetitive tasks. Technology Trends: new devices, social networking. PL has central role: 100 researchers may be busy for 20 years. If you share this vision too, please get in touch! 24

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#