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.