TU/e DBL Algorithms – 2014/15, Q2 Map Labeling

TU/e
DBL Algorithms – 2014/15, Q2
Map Labeling
Project coordinator:
Mark de Berg
TU/e
The project in a nutshell
solve complicated algorithmic problem in a team:
• design, analyze, and implement algorithm
• perform experimental evaluation
communicate solution
• write paper
• give presentation
professional skills
• 2PS12: Collaborating 2
• 2PS22: Presenting 2 training by STU
• 2PS42: Reflecting 2
• 2PS52: Planning and organizing 2
TU/e
Schedule, deliverables and grading scheme
week
day and time
activity (and location) or deadline
1 (Nov 10‒14)
Wed, hrs 5+6
kick-off meeting (Auditorium 11)
2 (Nov 17‒21)
Fri, 23:59
deadline for first prototype
3 (Nov 24‒28)
4 (Dec 1‒5)
5 (Dec 8‒12)
percentage of
team grade
no plenary meetings or special deadlines
Wed, hrs 5+6+7
training for mid-term presentations
group 1: Traverse 4
group 2 and 3: MetaForum 9
group 4 and 5: MetaForum 14
Fri, 23:59
deadline for interim report
Fri, 23:59
deadline for second prototype
Wed, hrs 5+6+7+8
mid-term presentations (Auditorium 11)
6 (Dec 15‒19)
no plenary meetings or special deadlines
Dec 22‒Jan 4
X-mas holiday
interim report: 10%
7 (Jan 5‒9)
Wed, hrs 5+6+7
training for final presentations
group 1: Traverse 3
group 2 and 3: Traverse 4
group 4 and 5: Traverse 5
8 (Jan 12‒16)
Mon, 23:59
deadline for software submission
Wed, hrs 5+6+7+8
final presentations (Auditorium 11)
9 (Jan 19‒23)
10 (Jan 26‒30)
mid-term presentations: 10%
output of software on test cases: 30%
final presentations: 10%
no plenary meetings or special deadlines
Wed, 23:59
deadline for reflection form prof. skills
Fri, 23:59
deadline for final report
final report: 40%
should be at least 5
TU/e
The project in a nutshell
other deliverables include
group planning and team sheets (every week)
minutes of meetings with tutor
test submissions
see course web page for more information
http://www.win.tue.nl/~mdberg/Teaching/DBL-Algorithms/2IO90-1415-Q2.htm
rest of today’s lecture
problem description
more info on the interim and final report
TU/e
Cartography in the old days
Historical map of the Netherlands (Johannes Janssonius 1658)
TU/e
Cartography: road maps
labeling is significant part of production time computer support desired
TU/e
Online / on-demand maps
online and on-demand mapping: cannot be done by hand
TU/e
Dynamic maps
labeling moving points: cannot be done by hand
TU/e
The DBL Project
1.566
1.099
1.433
1.350
0.799
1.773
1.350
0.765
2.275
3.333
1.089
2.882
1.200
1.494
DBL Setting: label points on a map with measurement values
labels are rectangles of fixed aspect ratio
TU/e
The DBL Project in more detail
Task: write program to label a given set of points
Requirement: labels do not overlap each other
Question: where are we allowed to place the labels?
TU/e
The DBL Project in more detail
Placement models
2-position model
4-position model
1-slider model
b
NW
NE
NW
NE
SW
SE
a
shift a/b can vary
between 0 and 1
TU/e
The difficulty
Mississippi delta
Arlington Arlington
Memphis Memphis
Memphis Memphis
30 cities:
430 = 1018 possibilities
TU/e
The DBL Project
Input
set of points (for each point: x- and y-coordinate)
placement model (1pos, 4pos, or 1slider)
aspect ratio
NW
NE
NW
NE
NE
NE
NE
NW
placement model: 2pos
aspect ratio: 1.6
NE
NW
Output
for each input point, the position of its label
label height, goal: maximize
Requirement
no two labels overlap (they can touch)
what if this is not possible?
TU/e
Software and grading
software must be written in Java and submitted through Peach
grading is done by running software on several test instances,
software design is not taken into account
─ eight tests for each of the three placement models
(two for each of n=10, n=25, n=100, n=10,000)
─ grade based on performance on these test cases
─ quality (i.e. label height) is main criterion
─ running time less important, but may also be taken into account
─ algorithm must terminate within 5 minutes
See problem description on web page for input and output format, etc
TU/e
The interim and final report
TU/e
Groups and tutor
assignment
TU/e
Tutor: Peter van Heck ([email protected])
Group 1 (time slot C+D)
Group 2 (time slot C+D)
Group 3 (time slot C+D)
1 Rick Bouten
1 Simin Chen
1 Björn Dullemond
2 Dennis Brons
2 Jeroen Donners
2 Pieter van der Heijden
3 Jeroen Brouns
3 Tim Segers
3 Robin Mennens
4 Melroy van Nijnatten
4 Aishwarya Suresh
4 Floris Schippers
5 Stephan Oostveen
5 Bart van der Vecht
5 Tasos Tsoukalas Stathakis
6 Jorrick Sleijster
6 René Zaal
Group 4 (time slot C+D)
Group 5 (time slot B+D)
1 Alex Dragomir
1 Tomas Sostak
2 Patrick Martin
2 Suraj Iyer
3 Lois Nijland
3 Jochem Kuijpers
4 Leroy Visser
4 Chris Tselepidas
5 Mert Zararsiz
5 Bart Verberne
Tutor: Jacco Snoeren ([email protected])

Download Report