Scribd
Upload
40 views11 pages

3.0 ALGO211 Week9 Computational Geometry

Computational geometry is a mathematical field focused on designing and analyzing algorithms for solving geometric problems, with applications in various domains such as computer graphics and robotics. The discipline emerged in the 1970s, with foundational work on algorithms for convex hulls and Voronoi diagrams. While primarily addressing two-dimensional problems, it has limitations in handling complex geometric shapes and focuses on efficient computation methods.

Uploaded by

pascuallynyer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
40 views11 pages

3.0 ALGO211 Week9 Computational Geometry

Computational geometry is a mathematical field focused on designing and analyzing algorithms for solving geometric problems, with applications in various domains such as computer graphics and robotics. The discipline emerged in the 1970s, with foundational work on algorithms for convex hulls and Voronoi diagrams. While primarily addressing two-dimensional problems, it has limitations in handling complex geometric shapes and focuses on efficient computation methods.

Uploaded by

pascuallynyer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Computation

al Geometry
What is computational
ComputationalGgeometry
e o m eistarmathematical
y? field
that involves the design, analysis and
implementation of efficient algorithms for solving
geometric input and output problems. It is
sometimes used to refer to pattern recognition
and describe the solid modeling algorithms used
for manipulating curves and surfaces.
What is computational
Is the branchG
of e o m e tscience
computer r y ? that studies
algorithms for solving geometric problems.
Applications:

• Computer graphics
• Ro b o t i c s
• VLSI design
• Computer Aided Design
• Molecular Modeling
• Metallurgy
• Manufacturing
• Te x t i l e l a y o u t s
• Fo re s tr y
• Statistics
A Concise History
• Most geometric algorithms less than 25 years old.
• 1970’s-Computational Geometry started as a
research discipline I the math programming,
theory/algorithms and CAD communities.

Earliest papers:
• Chand+kapur – Convex hull by gift wrapping
• Graham – Convex hull by graham scan
• Dpd+Lipton – Multidimensional searching
• Shamos – geometric computing
• Shamos + hoey – Voronoi Diagram
• Forrest – Computational Geometry

Better names: Algorithmic geometry


Geometric Algorithms
Limitations
• Computation-based geometry primarily deals with
flat and straight objects.

• The field mostly focuses on two-dimensional


problems, which are easy to visualize and
understand.
Intersection of lines – Detection of common
parts of objects – Usually linear (line segments,
polygons, n-gons,…)
p1 x p2=|x1 x2| = (x1y2) - (x2-y1) = -p2
x p1
|y1 y2|

• If p1 x p2 is positive the p1 is clockwise from p2 with


respect to origin (0,0) and if p1 x p2 is negative then
p1 is counterclockwise fro, p2 with respect to
origin(0,0)

• If cross product is zero then vectors p1 and p2 are


collinear pointing in either the same or opposite
direction.
Convex Hull | Set 1 (Jarvis’s
Algorithm or Wrapping)

Given a set of points in the plane. the convex hull of the


set is the smallest convex polygon that contains all the
points of it
The idea of Jarvis’s Algorithm is simple, we start from the
leftmost point (or point with minimum x coordinate
value) and we keep wrapping points in counterclockwise
direction.
Voronoi diagrams – Space (plane) partitioning into
regions whose points are nearest to the given primitive
(most usually a point)
How to find the answers

1. Prove hard and interesting theorems


2. Develop ideas and then look for a problem
that needs these ideas.
3. Build environments in which it is easier to
prove theorems.
4. Consider a problem from an application
and look for methods that can be used to
solve it.
5. Implement an algorithm, publicize your
code and ask people how they use it.
6. Build environments in which it is easier to
implement algorithms.

You might also like