
06560910
j
2016c.00972
Nasar, Audrey A.
A mathematical analysis of geometric algorithms.
Math. Comput. Educ. 49, No. 3, 157165 (2015).
2015
MATYC Journal, Old Bethpage, NY
EN
N70
G70
G90
U70
P20
computational geometry
discrete mathematics
algorithms
geometry
computer as educational medium
mathematical software
geometry software
convex hull problem
finite set of points
distance
giftwrapping algorithm
Jarvis's algorithm
Graham scan
closest pair problem
bruteforce algorithm
divideandconquer algorithm
distance comparisons
recurrence relations
Voronoi polygons
complexity functions
From the introduction: This paper presents a lesson in computational geometry for instructors of discrete mathematics and algorithms and can be presented to students who have taken College Algebra. Students can work with GeoGebra, or other dynamic geometry software, to depict a set of points in the plane. In order to investigate the `Convex Hull Problem' and the `Closest Pair Problem' discussed in this paper, students can use GeoGebra to construct the convex hull and find the distance between pairs of points. Computational geometry, which emerged in the 1970's, is a highly visual branch of computer science concerned with the design and analysis of algorithms for solving geometric problems. Geometric objects such as points, lines, and polygons are the basis of a broad variety of applications and give rise to an interesting set of problems and algorithms. Applications include but are not limited to computer graphics, robotics, geographic information systems, computer aided design, and computer aided manufacturing. We will present two fundamental problems that are used to solve many other problems in computational geometry. Both of these problems will seem trivial to the human eye, but for computers, who speak the language of algorithms, they are far less obvious.