Computational Geometry - CS 6/76110 
Spring 2025

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 
Telephone

Dr. Feodor Dragan 
Room 254 MSB
MW 10:30 am - 12:30 pm or by appointment


dragan at cs dot kent dot edu
(330) 672-9058

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.

  • Learning objectives: Students will learn (i) specific geometric structures that are the underlying models of several important applications; (ii) specific techniques and methods for designing efficient algorithms for solving geometric algorithmic problems; (iii) applications of computational geometry in robotics, graphics, CAD/CAM, VLSI layout, information visualization, bio-informatics and in wireless communication networks; (iv) new modern trends and challenges in design and analysis of geometric algorithms and data structures.
  • Prerequisites

Data Structures - CS 23001, Design & Analysis of Algorithms - CS 4/56101

  • Text

F.P. Preparata, M.I. Shamos, Computational Geometry: an introduction,  Springer-Verlag,  1993 (5th printing). (book)

  • Supplementary Text
    • J. O'Rourke, Computational Geometry in C, Cambridge  University Press, 1998 (Second Edition).
    • G.Di Battista, P. Eades, R. Tamassia, I.G. Tollis, Graph Drawing, Prentice-Hall, 1999.
    • M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, 1997.
    • Some recent journal papers.
  • Topics will include: This is a graduate level course. We will cover the following topics (the topics and order listed are tentative and subject to change).

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.

  • Course Requirements

HWs

- 

- 

- 

20% 

Presentations

-

-

-

20%

Midterm Exam

 TBA 

 March ??, 2025 

 12:30 pm - 1:45 pm

30% 

Final Exam

 Thursday

May 8, 2025

 10:15 am - 12:30 pm

30%
  • Milestone for successful completion of the course
    • Attend the classes regularly,
    • Perform the homework thoroughly and independently,
    • Read the book carefully and several times.
  • Registration Requirement:

The last day to add a full term class or change sections of a class is Jan. 19, 2025. [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. 26, 2025.

The last day to withdraw from course with grade of "W" assigned is March 30, 2025.

Spring Recess (No Classes): Mon-Sun, Mar 10-16, 2025.

  • Student Accessibility Policy: Kent State University is committed to inclusive and accessible educational experiences for all students. University Policy 3342-3-01.3 requires that students with disabilities be provided reasonable accommodations to ensure equal access to course content. Students with disabilities are encouraged to connect with Student Accessibility Services as early as possible to establish accommodations. If you anticipate or experience academic barriers based on a disability (including mental health, chronic medical conditions, or injuries), please let me know immediately.

 

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 2025

 

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.