id: 06560910
dt: j
an: 2016c.00972
au: Nasar, Audrey A.
ti: A mathematical analysis of geometric algorithms.
so: Math. Comput. Educ. 49, No. 3, 157-165 (2015).
py: 2015
pu: MATYC Journal, Old Bethpage, NY
la: EN
cc: N70 G70 G90 U70 P20
ut: computational geometry; discrete mathematics; algorithms; geometry;
computer as educational medium; mathematical software; geometry
software; convex hull problem; finite set of points; distance;
gift-wrapping algorithm; Jarvis’s algorithm; Graham scan; closest
pair problem; brute-force algorithm; divide-and-conquer algorithm;
distance comparisons; recurrence relations; Voronoi polygons;
complexity functions
ci:
li:
ab: 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.
rv: