Transcript CG_Lecture6 - Computer Science

UMass Lowell Computer Science 91.504
Advanced Algorithms
Computational Geometry
Prof. Karen Daniels
Spring, 2001
Lecture 6
Start of Part II Material
Monday, 2/4/01
Course Structure: 2 Parts
Basics
Polygon Triangulation
Partitioning
(2D and 3D) Convex
Hulls
Voronoi Diagrams
Arrangements
Search/Intersection
Motion Planning
Advanced Topics
Applications
Manufacturing
Modeling/Graphics
Wireless Networks
Visualization
Techniques
(de)Randomization
Approximation
Robustness
Representations
Epsilon-net
Decomposition tree
Syllabus (updated)
Lecture Date
Topics
Reading
Homework
Mon 4/2
Overview of Part II
Project Topics Overview
Assign project proposal
Mon 4/9
Project Topics
CG Libraries Overview
Tues 4/17
Mon 4/23
Mon 4/30
Mon 5/7
Mon 5/14
To Be
Determined
More Depth on Project Topics
More Depth on Project Topics
More Depth on Project Topics
Project Presentations
Review
Final Exam
handouts &
working group
report
handouts &
CG library
documentation
handouts
handouts
handouts
student handouts
Project proposals due
work on project
work on project
work on project
Project presentations due
Project writeups due
Cumulative
(open book)
Strategic Directions in Computational Geometry
Working Group Report
October, 1996
http://www.cs.brown.edu/people/rt/sdcr/report/report.html
Literature for Part II (current plan)
Aspect
Title
Milenkovic/Daniels Wu/Li
Translational
On
Polygon
calculating
Containment
connected
and Minimal
dominating
Enclosure
set for
using
efficient
Mathematical
routing in ad
Programming
hoc wireless
networks
Source
Journal: ITOR
Application
Areas
manufacturing
Input
Objects
2D nonconvex
polygons
Conf:
Workshop on
Discrete Alg
and Methods
for MOBILE
Computing
&
Communicati
ons
dynamic
wireless
communicati
ons
2D points
representing
hosts
Arya et al.
Goodrich/Ramos
An optimal algorithm
Boundedfor approximate nearest
Independence
neighbor searching in
Derandomization
fixed dimensions
of Geometric
Partitioning with
Applications to
Parallel FixedDimensional
Linear
Programming
Journal: ACM
Journal: Discrete
& Comp Geom
Shewchuck
Triangle: Engineering a 2D
Quality Mesh Generator and
Delaunay Triangulator
knowledge discovery;
data mining; pattern
recognition;
classification; machine
learning; data
compression;
multimedia databases;
document retrieval;
statistics
d-dimensional points
linear
programming
geometric modeling; graphics
range space
PSLG of object
Conf: 1st Workshop on Applied
CG
Literature for Part II (current plan)
(continued)
Aspect
Dimensional
ity
Problem/
Task
Milenkovic/Daniels Wu/Li
2D
2D
Theory?
Implementat
ion?
ADTs &
Data
Structures
Algorithmic
Paradigms
&
Techniques
Math Topics
Arya et al.
arbitrary
Goodrich/Ramos
arbitrary
Shewchuck
2D
translational
containment;
overlap
elimination;
distance-based
subdivision;
minimal
enclosure;
visibility
both
dominating
set
partitioning; nearestneighbor query
geometric
randomization;
geometric
derandomization
(constrained) Delaunay
triangulation; robustness
some
experiments
both
theory
implementation
convex hull;
visibility
polygon
undirected
graph
balanced boxdecomposition tree
epsilon-net;
epsilonapproximation
subdivision;
approximate
algorithm;
binary search
Minkowski
sum; linear
programming;
monotonicity;
convex
distance
function
distributed;
heuristic
geometric
preprocessing;
approximation
algorithm
Minkowski metric;
probability
randomization;
derandomization;
parallel
triangular mesh; (constrained)
Delaunay triangulation;
Voronoi diagram; convex hulls;
Guibas/Stolfi quad-edge;
triangular data structure; PSLG;
splay tree; heap
sweep-line; geometric divideand-conquer; incremental
insertion
graph theory:
dominating
set
VC-dimension;
linear
programming;
probability
duality
Project
Deliverable Due Date
Proposal
Interim Report
Final Presentation
Final Submission
Grade %
Monday, 4/9
Monday, 4/23
Monday, 5/7
Monday, 5/14
25% of course grade
2%
5%
8%
10%
Project Guidelines: Proposal



Objective: State the goal of the project
Plan: List the tasks you need to accomplish
and the date by which you plan to finish them
Resources: What do you need?





Specialized equipment, language, OS?
Specialized software/libraries?
Additional research papers, books?
More background in some area?
Assessment Checklist: Characterize your
project (see next 2 slides)
Guidelines: Proposal (continued)
 Assessment
Checklist:
 Characterize
Paradigm Design
Difficulty
 Analysis Technique Design
 Algorithm Design
Scope
Creativity
 Data Structure Design
 Algorithm and/or Data Structure Analysis
 correctness
Organization
Impact
 running time and/or space
Correctness
 Observations/Conjectures
Clarity
 Algorithmic
your project’s theoretical aspects:
Guidelines: Proposal (continued)
 Assessment
Checklist:
 Characterize
Clarity
your project’s implementation
aspects:
 Reuse
Creativity
Impact
of existing Code/Libraries
 New Code
 Experimental Design
 Test Suites
 Degenerate/boundary cases
 Numerical robustness
Difficulty
Scope
Organization
Correctness
Guidelines: Final Submission


Abstract: Concise overview (at most 1 page)
Introduction:





Motivation: Why did you choose this project?
Related Work: Context with respect to CG literature
Summary of Results
Main Body of Paper: (one or more sections)
Conclusion:
Summary: What did you accomplish?
 Future Work: What would you do if you had more time?
 References: Bibliography (papers, books that you used)

Well- written final submissions with research content may be
eligible for publishing as UMass Lowell CS technical reports.
Guidelines: Final Submission

Main Body of Paper:
 If
your project involves Theory/ Algorithm:
Informal algorithm description (& example)
 Pseudocode
 Analysis:


Correctness



Solutions generated by algorithm are correct
account for degenerate/boundary/special cases

If a correct solution exists, algorithm finds it

Control structures (loops, recursions,...) terminate correctly
Asymptotic Running Time and/or Space Usage
Guidelines: Final Submission

Main Body of Paper:
 If
your project involves Implementation:
Informal description
 Resources & Environment:



what language did you code in?

what existing code did you use? (software libraries, etc.)

what equipment did you use? (machine, OS, compiler)
Assumptions


parameter values
Test cases

tables, figures

representative examples
Guidelines: Interim Report

Structured like Final Submission, except:
 no Abstract
or Conclusion
 fill in only what you’ve done so far
 can be revised later
 include a revised proposal if needed
 identify any issues you have encountered and
your plan for resolving them
Guidelines: Presentation




1/2 hour class presentation
Explain to the class what you did
Structure it any way you like!
Some ideas:



slides (electronic or transparency)
demo
handouts
Project Topics (some possibilities)
Build on a Part I assignment, such as random
point assignments in 2D or 3D
 Navigate A  (  B ) based on line arrangement to
do combinatorially-based overlap increase or
reduction
 Visualization: Can geometric duality help with
parallel coordinate representation of highdimensional data?

Project Topics (some possibilities)

Dynamic Wireless Channel Assignment:
 design
a heuristic that, given an assignment of
frequencies to regions, transforms it into another
assignment that:
satisfies a given demand level (number of frequencies) for
each region
 respects a separation constraint
 “minimizes” the number of frequencies
 ‘minimizes” the number of frequency reassignments
