Computational
Geometry - CS 6/76110
Spring 2024
MW 12:30
pm - 1:45 pm, MSB Room 115
Office hours: MW
10:30 am - 12:30 pm or by appointment
Instructor Office Hours Email |
Dr. Feodor Dragan
|
Geometric structures are the
underlying model of several important applications, including
robotics, graphics, CAD/CAM, VLSI layout,
and information visualization. The field of computational
geometry, which studies algorithms for geometric problems, has
attracted increasing research interest in the last years, and is
currently one of the most active areas of investigation in theoretical
computer science. The course focuses on two-dimensional geometry.
Data Structures - CS
23001, Design & Analysis of Algorithms - CS 4/56101
F.P. Preparata,
M.I. Shamos, Computational Geometry: an introduction, Springer-Verlag,
1993 (5th printing). (book)
Basic Geometric Concepts:
points, lines, polygons; subdivisions; arrangements; polytopes; cell complexes.
Geometric Searching: fractional cascading; segment
tree; interval tree, range tree; priority search tree.
Point Location: slab method; trapezoid method;
chain method; bridged chain method.
Plane-Sweep Algorithms: intersection of segments;
intersection of rectangles; trapezoidation.
Convex Hulls: 2-dimensional convex hull; dynamic
convex hull; 3-dimensional convex hull.
Proximity: closest pair; furthest pair;
Voronoi diagrams; triangulations.
Applications: Computational Geometry methods in
Wireless networks
Graph Drawing: planar drawings; straight-line
drawings; orthogonal drawings; polyline drawings.
Visibility Graphs: shortest paths; computing
visibility graphs.
HWs |
- |
- |
- |
20% |
Presentations
|
- |
- |
- |
20% |
Midterm
Exam |
TBA |
March
??, 2024 |
12:30 pm - 1:45 pm |
30% |
Final
Exam |
Wednesday |
May 8, 2024 |
10:15 am - 12:30 pm |
30% |
The
last day to add a full term class or change sections
of a class is Jan. 22, 2024. [University policy requires all students to be
officially registered in each class they are attending. Students who are not
officially registered for a course should not be attending classes and will not
receive credit or a grade for the course. Each student must confirm enrollment
by checking his/her class schedule (using Student Tools in FlashFast)
prior to the deadline indicated. Registration errors must be corrected prior to
the deadline.]
The
last day to withdraw from course before grade of "W" is assigned is
Jan. 29, 2024.
The last day to withdraw from course with grade of "W"
assigned is Apr. 1, 2024.
Spring Recess (No Classes): Mon-Sun, Mar. 25 - Mar. 31, 2024.
Student Accessibility Services
(SAS) Contact Information:
Location: University Library,
Suite 100
Email: sas@kent.edu
Phone: 330-672-3391; VP 330-968-0490
Web: www.kent.edu/sas
F. Dragan
dragan at
cs.kent.edu
Spring 2024
NOTICE
OF MY COPYRIGHT AND INTELLECTUAL PROPERTY RIGHTS. Any intellectual
property displayed or distributed to students during this
course (including but not limited to powerpoint
presentations, notes, quizzes, examinations) by the professor remains the
intellectual property of the professor. This means that the student may
not distribute, publish or provide such intellectual property to any
other person or entity for any reason, commercial or otherwise, without the
express written permission of the professor.