Algorithmische Geometrie

Algorithmische Geometrie, Sommersemester 2014

# Erster Teil

Das Sweep-Verfahren der algorithmischen Geometrie

Closest Pair of Points | Divide and Conquer | GeeksforGeeks

Computational Geometry – Line Sweep – 2 – Segments Intersection (Arabic)

Sweep line algorithm part 1

Sweep line algorithm part 2

Coding Math: Episode 32 – Line Intersections Part I

Coding Math: Episode 33 – Line Intersections Part II

11 2 Line Segment Intersection 546

11 1 1d Range Search 851

11 3 Kd Trees 2907

11 4 Interval Search Trees 1347

Given n line segments, find if any two segments intersect

Algorithmen und Datenstrukturen – Suchbaum (PDF)

MIT: Introduction to Algorithms – Lecture 24: Geometry (PDF)

Wikipedia – Binärer Suchbaum

Point location

Point set triangulation

Planar straight-line graph

Voronoi diagram

Voronoi-Diagramm

Delaunay triangulation

Delaunay-Triangulierung

# Woche 1

time complexity

Analysis of Algorithms: Average Case Analysis

Analysis of Algorithms

Analysis of Algorithms | Set 1 (Asymptotic Analysis)

Analysis of Algorithms | Set 2 (Worst, Average and Best Cases)

ec 1 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005

Time complexity

Zeitkomplexität

Laufzeit (Informatik)

Sortierverfahren

codeadventurer.de

codeadventurer.de: Die O Notation. Wie schnell ist dein Code?

How to analyse time complexity: Count your steps

Time complexity of recursive functions [Master theorem]

Big O notation: definition and examples

Zeitkomplexität und O-Notation

Analysis of Algorithms

2.3. Big-O Notation

Problem Solving with Algorithms and Data Structures using Python

2d line intersection

Line–line intersection

How do you detect where two line segments intersect? [closed]

Line and Segment Intersections

# Woche 2

Sweep (Informatik) (Sweep-Line)

Rot-Schwarz-Baum (red–black tree oder RB tree)

Wikipedia: JTS Topology Suite

LocationTech JTS Topology Suite

JavaDoc JTS Topology Suite 1.15.0-SNAPSHOT API

github.io JTS Topology Suite

JTS Frequently Asked Questions

github.com/locationtech/jts, The JTS Topology Suite is a Java library for creating and manipulating vector geometry.

github.com/locationtech/jts/releases

github.com/locationtech/jts/blob/master/MIGRATION.md

github.com/locationtech/jts/blob/master/USING.md

github.com/locationtech/jts/blob/master/DEVELOPING.md

GIS Wiki: Java Topology Suite

OSGeoLive JTS Topology Suite

Wikipedia: Open Source Geospatial Foundation (OSGeo)

OSGeo – The Open Source Geospatial Foundation

OSGeo Libraries (GEOS, JTS Topology Suite)

### Aufgabe 1

Array sortieren mit Java

Converting between an Array and a List in Java

A Guide to TreeSet in Java

TreeSet in Java

Binary Search Tree Complete Implementation

Binary Search Tree – Java Implementation

# Woche 4

Truncation (geometry)

Archimedean solid

Conway polyhedron notation

# Woche 8

Problem

Optimierungsproblem

Suchproblem

Heuristik

Komplexitätsklasse

Liste von Komplexitätsklassen

NP (Komplexitätsklasse)

NP-Schwere, NP-hard

P-NP-Problem

Polynomialzeit

Polynom

Laufzeit (Informatik)

Zeitkomplexität

Landau-Symbole

, Max-Flow

Google OR-Tools: Job Shop

Sequencing and Scheduling – Johnson’s Algorithm

ICAPS 2015: “Iterated Local Search Heuristics for Minimizing Total Completion Time in …”

Michael Sambol Algorithms

4. Search: Depth-First, Hill Climbing, Beam

Representing graphs

Graph and its representations

Graph Representation part 01 – Edge List

Graph representation. set, adjacency matrix and adjacency list

Data Structures using C Part 29 – Adjacency List Representation of Graph in c programming

Meta-Heuristic Optimization Techniques and Its Applications in Robotics

Asymptotische Komplexität

Obere und untere Schranken

Approximation algorithms – Heuristic Algorithms (PDF)

Wikipedia: Approximation algorithm

Wikipedia: Algorithmus von Christofides

ApproximationAlgorithms

What does the 2 in a 2-approximation algorithm mean?

Algorithmen und Datenstrukturen

Erdős-Zahl

Bacon-Zahl

# Woche 9

https://github.com/jackspyder/2-opt, Java 2-opt solution for TSP Coursework

2-opt

Lin–Kernighan heuristic, K. Helsgaun (LKH), LK local search

# Woche 11

github.com/thiagodnf/jacof, Java Ant Colony Optimization Framework

github.com/LazoCoder/Ant-Colony-Optimization-for-the-Traveling-Salesman-Problem, A population based stochastic algorithm for solving the Traveling Salesman Problem

TSP ACO Applet

Ant Colony Optimization Tutorial

github.com/eugenp/tutorials/tree/master/algorithms-genetic

# Woche 12

Steinerbaumproblem

Santa’s Stolen Sleigh

Geographische Länge

Geographische Breite

Geographische Koordinaten, Geographische Lage

Gradnetz

Hilbert R-tree

R-Baum, R-tree

Environment for DeveLoping KDD-Applications Supported by Index-Structures (ELKI)

Closest pair of points problem

Dichtestes Punktpaar

# Woche 13

github.com/OSUCartography/JMapProjLib, JMapProjLib: Java Map Projection Library

Converting longitude/latitude to X/Y coordinate

Convert latitude/longitude point to a pixels (x,y) on mercator projection

Mercator projection

Mercator-Projektion

### C

PROJ – a generic coordinate transformation software

github.com/OSGeo/proj.4, PROJ.4 – Cartographic Projections Library

PROJ.4

Lat/long (Geodetic alias)

Mercator

### Java OpenGL

Java OpenGL (JOGL)

Where can I find the package javax.media.opengl?

### JavaFX

- Sphere
- PhongMaterial
- RotateTransition
- PointLight

Position of PerspectiveCamera in JavaFX 8

JAVA PROGRAMMING: ADD, ANIMATE, AND LIGHT UP OBJECTS IN 3D

### PHP

github.com/mfeldheim/hermap, Hermap libraries: stuff related to maps

### R

Overview of Coordinate Reference Systems (CRS) in R (PDF)

R Spatial – Coordinate Reference Systems

Choosing the correct value for proj4string for shapefile reading in R?