\input zb-basic
\input zb-matheduc
\iteman{ZMATH 2016c.00972}
\itemau{Nasar, Audrey A.}
\itemti{A mathematical analysis of geometric algorithms.}
\itemso{Math. Comput. Educ. 49, No. 3, 157-165 (2015).}
\itemab
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.
\itemrv{~}
\itemcc{N70 G70 G90 U70 P20}
\itemut{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}
\itemli{}
\end