Algorithmische Geometrie
Algorithmische Geometrie, Sommersemester 2014
Computational Geometry, Summer 2018
Geometric Algorithms (INFOGA) 2018, Block 2, Frank Staals
Vier Lerntypen
Wahrnehmung
Die vier Lerntypen
Die vier Lerntypen – der auditive Lerntyp
Die vier Lerntypen – der visuelle Lerntyp
Die vier Lerntypen – der haptische Lerntyp
Die vier Lerntypen – der kommunikative Lerntyp
Erster Teil
Algorithmen 1
Algorithmen 1, Vorlesung, SS 2019, 27.07.2019
21: Übung: Ameisenalgorithmen, Vertex Cover, Nachbarschaftsmetaheuristiken, 2.07.2017
Algorithmen 2
Algorithmen 2, Vorlesung, WS2017/18, 08.02.2018
Algorithmen 2, WS 2018/19, 01.08.2019
19: Geometrische Algorithmen, Streckenschnitt, Überlappungen, 07.02.2019
20: Streckenschnitt, Konvexe Hülle, Geometrische Methoden, Übung, 12.02.2019
23: Online Algorithmen, Geometrische Algorithmen, Streckenschnitt, 26.01.2017
24: Konvexe Hüllen, Bereichssuche, Kleinste einschließende Kugel, 26.01.2017
25: Wavelet Tree, Sweepline, Linienschnitt, Geometrische Algorithmen,01.02.2017
Das Sweep-Verfahren der algorithmischen Geometrie
Closest Pair of Points | Divide and Conquer | GeeksforGeeks
Computational Geometry Lec 4 ( Sweep Line Algorithm ) ( in Arabic )
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: Best and Worst cases | Quick Sort | GateAppliedcourse
Stochastik Übersicht, Wahrscheinlichkeit, beschreibende/beurteilende Statistik
Kombinatorik, Permutation mit Wiederholung, Beispiel am Wort Wetter | Mathe by Daniel Jung
Kombinatorik, Permutation, Variation, Kombination, Beispiele, Abzählverfahren | Mathe by Daniel Jung
Comparison sorts
Simple sorts
- Insertion sort
- Selection sort
Efficient sorts
- Merge sort
- Heap sort
- Quick sort
Bubble sort
- Bubble sort
Exotic sorts
- Binary tree sort
- Cycle sort
- Library sort
- Patience sort
- Smooth sort
- Strand sort
- Tournament sort
- Cocktail sort
- Comb sort
- Gnome sort
- Block sort
- Odd–even sort
- Curve sort
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
Aufgabe 1
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
Convex Hull – Divide & Conquer
Convex hull algorithms
Complexity of the QuickHull Algorithm?
Convex Hull Algorithms: Divide and Conquer
Divide and Conquer algorithm to find Convex Hull
Quick Hull Algorithm to find Convex Hull
Quickhull Algorithm for Convex Hull
Convex Hull using Divide and Conquer Algorithm
Tangents between two Convex Polygons
Convex Hull, COMP 215 Lecture 5, PDF
An efficient way of merging two convex hulls
Tangents to & between 2D Polygons
Woche 3
Wikipedia
Planarer Graph
Dreiecksgraph
Eulerscher Polyedersatz
Vollständiger Graph
Grad (Graphentheorie)
Line segment intersection
Bentley–Ottmann algorithm
Schleife (Graphentheorie)
Zyklus (Graphentheorie)
Dreieckszahl
Satz von Kuratowski
Satz von Wagner
Bipartiter Graph
Line Segment Intersection (LSI)
Freie Universität Berlin – Computational Geometry: Line segment intersection
The intersection of two line segments
YouTube
Mathematik (WiSe 2013/2014 und SoSe 2014) (Playlist)
Planare Graphen
Vollständige Graphen
Woche 4
Graph (Graphentheorie)
Nachbarschaft (Graphentheorie)
Isomorphie von Graphen
Planar graph
Cycle graph
Star (graph theory)
Wheel graph
Cubic graph
Ladder graph
Category:Planar graphs
Category:Triangulation (geometry)
List of graphs by edges and vertices
Doubly-connected edge list
Half-Edge-Datenstruktur
Wolfram MathWorld
Star Graph
Wheel Graph
Cubical Graph
Platonic Graph
Hypercube Graph
Halved Cube Graph
Graph
Families of Graphs (PDF)
DCEL
Freie Universität Berlin – DCEL: Eine Datenstruktur für ebene Unterteilungen (PDF)
Plane Graphs and the DCEL (PDF)
Computergeometrie (Senior)
Computergeometrie (Senior) (übersetzt!)
Index of /farshi/Teaching/CG3921/Slides
Computing the Overlay of Two Subdivisions
Geometric Algorithms (INFOGA) 2018, Block 2
Computational Geometry – Lecture 2b: Subdivision representation and map overlay
Overlay of Two Subdivisions – PowerPoint PPT Presentation
CGAL
2D Arrangements – Arrangement on Surface
Truncation (geometry)
Archimedean solid
Conway polyhedron notation
YouTube
Sarada Herke
Graph Theory: 04. Families of Graphs
Graph Theory: 07 Adjacency Matrix and Incidence Matrix
Graph Theory: 27. Hamiltonian Graphs and Problem Set
Graph Theory: 57. Planar Graphs
Graph Theory: 61. Characterization of Planar Graphs
Do Maths with Pigeons and Handshakes
Maths Resource
Planar Graphs – Worked Examples
freeCodeCamp.org
Algorithms Course – Graph Theory Tutorial from a Google Engineer (6:44:39) => 6h!
SDMLab
mycodeschool
Data structures
Graph Representation part 01 – Edge List
Graph Representation part 02 – Adjacency Matrix
Graph Representation part 03 – Adjacency List
Gokul Raghuraman
Planar mesh data structure that uses vertices, half-edges and faces
UC Davis Academics
Woche 5
Freie Universität Berlin – Lecture 4 (CGAL)
CGAL
2D Triangulation
github.com/CGAL/cgal/tree/master/Triangulation_2/examples/Triangulation_2
Woche 6
Woche 7
Heap (Datenstruktur)
Min-Max-Heap
Vorrangwarteschlange
Stapelspeicher
14_Algorithmen&Datenstrukturen || Heap (Aufbau & Daten einfügen)
15_Algorithmen&Datenstrukturen || Heap (Daten löschen & Arraydarstellung)
Vorrangwarteschlange
Priority Queue Introduction
2.6.3 Heap – Heap Sort – Heapify – Priority Queues
Fastest Sorting Algorithm. Ever!
AlgoDat – 03: Heaps, Heapify-Funktion und Heapsort mit Beispiel und Code (C#)
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
Single-machine scheduling, Performance measures: Tardiness, Earliness, Lateness Flowtime
Google OR-Tools: Job Shop
Sequencing and Scheduling – Johnson’s Algorithm
Job Sequencing Problem with Deadline, Greedy Algorithm
ICAPS 2015: “Iterated Local Search Heuristics for Minimizing Total Completion Time in …”
Michael Sambol Algorithms
4. Search: Depth-First, Hill Climbing, Beam (Beam Search: 35:15)
Hill Climbing – Bergsteigeralgorithmus Suchalgorithmen
beam search, search wrap up (4:30)
Solution Space Search,Beam Search
What is Beam search in artificial intelligence in hindi | lec 14 | Nauman Malik | CS607 | easy methd
mod10lec83-Beam Search (not exactly)
Beam Search Algorithm (Draft by Andrew Jungwirth)
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
H.W. Lang Hochschule Flensburg
Algorithmen
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
Interval Partitioning ( Greedy Algorithm ) – Algorithms
Rate Monotonic Scheduling
Sequencing Problem For More than 3 Machines|| Processing n Jobs on m Machines By JOLLY Coaching
Minimum tardiness problem
Scheduling with deadlines: minimizing lateness
Dijkstra’s Algorithm ( incl. Example and Step-By-Step Guide ) – Algorithms
Sequencing n jobs on 1 machine – Example 2
N jobs and 2 machines using Johnson’s algorithm in Hindi ( Lecture.40)
n jobs and 3 machines ( Johnson’s algorithm ) in Hindi ( Lecture.41)
Woche 9
- Maximum Regret
- Branch-and-bound
- Branch-and-cut
Graph traversal
Tree traversal
Search tree
https://github.com/jackspyder/2-opt, Java 2-opt solution for TSP Coursework
2-opt
Lin–Kernighan heuristic, K. Helsgaun (LKH), LK local search
Complexity Zoo
APX
Optimierungsproblem
Kombinatorische Optimierung
Optimierung (Mathematik)
Approximationsalgorithmus
Time complexity – Polynomial time
Polynomial-time approximation scheme
List of NP-complete problems
NP-completeness
Linear programming
Dynamic programming
Knoten mit gegebenen Kanten
Breitensuche, (breadth-first search, BFS)
Tiefensuche, (depth-first search, DFS)
Iterative Tiefensuche, (Iterative Tiefensuche)
Bestensuche, (best-first search)
Knoten ohne Kanten, resp. mit einem vollständigen Graph
Nearest neighbor search
Suchverfahren, Informierte Suche = Heuristik
Woche 10
A Practical Introduction to Simulated Annealing
A Practical Introduction to Genetic Algorithms
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
meta-heuristics
Lineare Optimierung, Simplex-Verfahren, Operations Research (Linear Programming)
Quadratic Assignment Problem
Quadratic assignment problem
Quadratic Assignment Problem
Quadratic Assignment on Different Data Models
Yuehaw Khoo — Clique-Based Semidefinite Relaxation of the Quadratic Assignment Problem
Assignment Problem / Branch and Bound
Assignment Problem using Branch and Bound
Assignment problem by branch and bound method
7.3 Traveling Salesman Problem – Branch and Bound
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?
John Levine
- CS103: Proof by Induction
- CS103: Another Direct Proof
- CS103: Direct Proof
- CS103: Infinite Sets and Definitions
- Iterative Deepening
- Depth First Search
- Breadth First Search – Part 2
- Breadth First Search – Part 1
- A* Search
- Uniform Cost Search
- Minimax with Alpha Beta Pruning
- Monte Carlo Tree Search
Dynamic Programming
What Is Dynamic Programming and How To Use It
Other Metaheuristics
Learn Particle Swarm Optimization (PSO) in 20 minutes
Artificial Bee Colony (ABC) Visualized – Artificial Intelligence
Honey Bee Optimization (HBO) Algorithm
Bat Algorithm BA
HackerRank
- Recursion
- Solve ‘Ice Cream Parlor’ Using Binary Search
- Binary Search
- Solve ‘Shortest Reach’ Using BFS
- Solve ‘Connected Cells’ Using DFS
- Solve ‘Recursive Staircase’ Using Recursion
- Quicksort
- Merge Sort
- Bubble Sort
- Solve ‘Coin Change’ Using Memoization and DP
- Memoization and Dynamic Programming
- Sort An Array with Comparator
- Bit Manipulation
- Graph Search, DFS and BFS
- Solve ‘Lonley Integer’ Using Bit Manipulation
- Balanced Parentheses in Expression
- Queue With Two Stacks
- Stacks and Queues
- Cycles in a Linked List
- Linked Lists
- Binary Search Tree
- Trees
- Solve ‘Contacts’ Using Tries
- Tries
- Heaps
- Solve ‘Find the Running Median’ Using Heaps
- Anagram Problem Solution
- Hash Tables
- Solve ‘Ransom Note’ Using Hash Tables
Scheduling / Project Planning / Critical Path
Scheduling projects: How to determine the critical path using activity slack calculations?
Activity slack: Total, safety and free slack definitions
Scheduling, precedence diagramming and the critical path
How to Calculate Critical Path, Float, Early Start & Late Start, and Early Finish & Late Finish
Understanding Critical Path in Project Management (Example Included)
he Ultimate Guide to the Critical Path Method
Netzplan / Kritischer Pfad
Statt Projekte mit Arbeitspaketen nun nur Abhängigkeiten zwischen Tasks in EINEM Job. Etwas anderes Problem Projektplan/Netzplan vs. Scheduling.
Netzplan | Kritischer Pfad | Beispiel | Berechnung | Produktion (2/3) | Einfach sehr gut erklärt!
Kritischer Pfad im Projektablauf