Dr. Feodor F. Dragan
Professor of
Computer Science
Feodor F. Dragan received the M.S. degree in Applied
Mathematics and Computer Science from Moldova State University, in 1985, and
the PhD degree in Theoretical Computer Science from the Belorussian Academy of
Sciences, in 1990. He was an Assistant and then an Associate Professor at the
Mathematics and Computer Science Department of Moldova State University from
1988 to 1999. From 1994 to 1999, he was on leave of absence and worked in
Germany as a Research Associate on a Volkswagen Foundation (VW) project and on
a German Research Community (DFG) project. He was also awarded a DAAD Research
Fellowship (Germany) from 1994 to 1995. During 1999 to
2000, he was a Research Associate at the Computer Science Department of
University of California, Los Angeles. Since August 2000 he has been with Kent
State University and he is currently a Professor of
Computer Science. He held visiting positions in
Germany (Technische Universitaet Berlin), in France (Universite de la Mediterranee, Marseille and
Universite Paris Diderot - Paris 7), in Norway (Universitetet i Bergen), and in Chile (Universidad de Chile, Santiago). He has authored
more than 150 refereed scientific publications. His
research interests include design and analysis of network algorithms,
algorithmic graph and hypergraph theory, computational geometry, computational
biology, VLSI CAD, combinatorial optimization, discrete convexity and geometry
of discrete metric spaces, distance location problems and operations research,
data analysis.
Computational
Geometry - CS 6/76110
Spring 2026
MW 12:30
pm - 1:45 pm, MSB Room 121
Office hours:
MW 1:45 pm - 3: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.
- 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,
- 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
??, 2026 |
12:30 pm - 1:45 pm |
30% |
|
Final
Exam |
Friday |
May 8, 2026 |
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. 18, 2026. [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. 25, 2026.
The last day to withdraw from course with grade of "W"
assigned is Mar. 29, 2026.
Spring Recess (No Classes): Mon, Mar 09,
2026 - Sun, Mar 15, 2026.
- SSI is now online: The Student Survey of Instruction (SSI) is now online.
You will be given time to complete that survey on-line
during the last class meeting.
- 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
Student
Cheating and Plagiarism
University policy states that "students enrolled in the university, at all its campuses,
are to perform their academic work according to standards set by faculty
members, departments, schools and colleges of the university; and cheating and
plagiarism constitute fraudulent misrepresentation for which no credit can be
given and for which appropriate sanctions are warranted and will be applied.
"Cheat" means intentionally to misrepresent the source, nature, or
other conditions of academic work so as to accrue
undeserved credit, or to cooperate with someone else in such misrepresentation.
Such misrepresentations may, but need not necessarily,
involve the work of others. "Plagiarize" means to take and present as
one's own a material portion of the ideas or words of
another (e.g. person, persons, or Generative Artificial Intelligence), or to
present as one's own an idea or work derived from an existing source without
full and proper credit to the source of the ideas, words, or works."
See the complete university
policy regarding cheating and plagiarism, which in addition to the above
contains detailed definitions and information about sanctions.
Title IX
Kent State is committed to
fostering a safe, productive learning environment. As an instructor, one of my
responsibilities is to help create a safe learning environment in our class.
Kent State (and federal law Title IX) policy prohibit discrimination based on
sex, which includes sexual misconduct - (sexual harassment, domestic and dating
violence, sexual assault, and stalking). We understand that sexual violence can
undermine students academic
success and we encourage students who have experienced some form of sexual
misconduct to talk to someone about their experience, so they can get the
support they need.
It is my goal that you feel able
to share information related to your life experiences in classroom discussions,
in your written work, and in our one-on-one meetings. I will seek to keep the
information you share private to the greatest extent possible. However, I also
have a responsibility to notify the Title IX Coordinator when I become aware of
incidents of sexual misconduct. Students may speak privately (without
disclosing name) to the Center for Sexual and Relationship Violence Support
Services (SRVSS) 330-672-8016. Learn more
about SRVSS. Students may speak confidentially to Psychological Services
330-672-2487. Another resource available to help navigate issues and concerns
is the Student Ombuds. (330-672-9494). Read a message
from the Student Ombuds .
Request for Religious
Accommodations
The University welcomes
individuals from all different faiths, philosophies, religious traditions, and
other systems of belief, and supports their respective practices. In compliance
with university policy and the Ohio Revised Code, the University permits
students to request class absences for up to three (3) days, per term, in order to participate in organized activities conducted
under the auspices of a religious denomination, church, or other religious or
spiritual organization. Students will not be penalized as a
result of any of these excused absences.
The request for excusal must be
made in writing during the first fourteen (14) days of the semester and include
the date(s) of each proposed absence or request for alternative religious
accommodation. The request must clearly state that the proposed absence is to
participate in religious activities. The request must also provide the particular accommodation(s) you desire.
You will be notified by me if your
request is approved, or, if it is approved with
modification. I will work with you in an effort to arrange a mutually agreeable alternative arrangement. For
more information regarding this Policy you may contact the Student Ombuds (ombuds@kent.edu).
F. Dragan
dragan at
cs.kent.edu
Spring 2026
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.