Computational
Geometry - CS 6/76110
Spring 2021
MW 5:30 pm - 6:45 pm
REMOTE
Instructor Office Hours
|
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).
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 ??, 2021 |
5:30 pm - 6:45 pm |
30% |
Final Exam |
Monday |
May 10, 2021 |
5:45 pm - 8:00 pm |
30% |
The last day to add a full term class or change
sections of a class is Jan. 25, 2021. [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 Feb. 1, 2021.
The last day to withdraw from
course with grade of "W" assigned is March 29, 2021.
Spring Recess (No Classes): Apr.
12 - Apr. 18, 2021.
Cheating
and plagiarism constitute fraudulent misrepresentation for which no credit can
be given and for which appropriate sanctions are warranted and will be applied.
The university affirms that acts of cheating and plagiarism by students
constitute a subversion of the goals of the institution, have no place in the
university and are serious offenses to academic goals and objectives, as well
as to the rights of fellow students.
"Cheat"
means to intentionally 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. Cheating includes, but is not limited to:
1. Obtaining or
retaining partial or whole copies of examinations, tests or quizzes before
these are distributed for student use;
2. Using notes,
textbooks or other information in examinations, tests and quizzes, except as
expressly permitted;
3. Obtaining
confidential information about examinations, tests or quizzes other than that
released by the instructor;
4. Securing,
giving or exchanging information during examinations;
5. Presenting
data or other material gathered by another person or group as one's own;
6. Falsifying
experimental data or information;
7. Having
another person take one's place for any academic performance without the
specific knowledge and permission of the instructor;
8. Cooperating
with another to do one or more of the above;
9. Using a
substantial portion of a piece of work previously submitted for another course
or program to meet the requirements of the present course or program without
notifying the instructor to whom the work is presented; and
10. Presenting
falsified information in order to postpone or avoid examinations, tests,
quizzes, or other academic work.
"Plagiarize"
means to take and present as one's own a material portion of the ideas or words
of another 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. As defined, plagiarize includes, but is not limited to:
a.
The copying of words, sentences and paragraphs directly from
the work of another without proper credit;
b. The copying
of illustrations, figures, photographs, drawings, models, or other visual and
nonverbal materials, including recordings of another without proper credit; and
c.
The presentation of work prepared by another in final or
draft form as one's own without citing the source, such as the use of purchased
research papers.
Academic Sanctions, From Section D The
following academic sanctions are provided by this rule for offenses of cheating
or plagiarism.
1. Refuse to
accept the work for credit; or
2. Assign a
grade of "F" or zero for the project, test, paper, examination or
other work in which the cheating or plagiarism took place; or
3. Assign a
grade of "F" for the course in which the cheating or plagiarism took
place; and/or;
4. Recommend to
the department chair or regional campus dean that further action specified in
the rule be taken. The department chairperson or regional campus dean shall
determine whether or not to forward to the academic dean or to the vice
president for the extended university a recommendation for further sanction
under this rule.
Procedures for invoking sanctions. (From Section E)
(1)
Academic
administrative procedures pertaining to paragraph (D)(1)(a)
of this rule. In the event that an instructor determines that it is more
probable than not that a student in a course or program under the instructor's
supervision has presented work for university credit which involves an act of
cheating, plagiarism or cooperation in either, then the instructor shall:
(a)
Inform the
student as soon as is practical, in person or by mail, of the belief that an
act of cheating or plagiarism has occurred. If the student cannot be reached in
a reasonable period of time, the instructor may proceed with sanctions,
notifying the student in writing as promptly as possible of the belief and the
procedural steps the instructor has taken.
(b)
Provide the student an opportunity to explain orally, in
writing, or both, why the student believes the evaluation of the facts is
erroneous.
(c)
If the
explanation is deemed by the instructor to be inadequate or if no explanation
is offered, the instructor may impose one of the academic sanctions listed in
paragraph (D)(1)(a) of this rule. Where appropriate,
the instructor may recommend the imposition of academic sanctions listed in
paragraph (D)(1)(b) of this rule. In addition, the
instructor may refer the matter to the dean of the college, campus, or school
in which the student is enrolled for imposition of academic sanctions listed in
paragraph (D)(1)(b) of this rule.
(d)
The instructor
shall notify the office of judicial affairs of the circumstances and action
taken. Such notification will be used as background information in the event
that formal conduct charges are initiated against the student.
(e)
The instructor
shall inform the student in writing of the right to appeal, and the procedure
to follow.
(f)
The instructor
shall keep the evidence of cheating or plagiarism in a secure place and provide
it upon request to any appeals officer or the conduct officer. The instructor
shall provide copies on request to the student at the student's expense.
(g)
The instructor
shall cooperate with academic and student conduct personnel in any appeal of
the decision, and/or in adjudication of any disciplinary proceedings.
F.
Dragan
dragan at
cs.kent.edu
Spring
2021
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.