100% tevredenheidsgarantie Direct beschikbaar na betaling Zowel online als in PDF Je zit nergens aan vast
logo-home
Summary Geometric Algorithms €9,99
In winkelwagen

Samenvatting

Summary Geometric Algorithms

 13 keer bekeken  0 keer verkocht

High quality summary covering the entire Geometric Algorithms course. All of the concepts are clearly, yet compactly summarized, and explained in more detail where necessary. Based on the lectures, slides and the associated book.

Laatste update van het document: 10 maanden geleden

Voorbeeld 4 van de 34  pagina's

  • Nee
  • Chapter 1 through 11
  • 27 januari 2024
  • 3 februari 2024
  • 34
  • 2023/2024
  • Samenvatting
book image

Titel boek:

Auteur(s):

  • Uitgave:
  • ISBN:
  • Druk:
Alle documenten voor dit vak (1)
avatar-seller
Suniht
‭Geometric Algorithms‬
‭ asics‬
B ‭‬
2
‭Convex hulls‬ ‭3‬
‭Map overlay‬ ‭4‬
‭Line segment intersection‬ ‭4‬
‭Doubly-connected edge list‬ ‭5‬
‭Overlaying the maps‬ ‭8‬
‭Polygon triangulation‬ ‭10‬
‭Polyhedron casting‬ ‭13‬
‭Enclosing circles‬ ‭15‬
‭Vertical decomposition‬ ‭17‬
‭Range searching‬ ‭20‬
‭KD-trees‬ ‭20‬
‭Range trees‬ ‭23‬
‭Voronoi diagram‬ ‭25‬
‭Delaunay triangulations‬ ‭27‬
‭Duality and arrangements‬ ‭30‬
‭Windowing queries‬ ‭33‬

,‭Basics‬
‭Definitions‬
‭-‬ ‭Plane‬‭= 2D space‬
‭-‬ ‭Point‬‭= set of coordinates (depending on 2D, 3D etc.)‬
‭-‬ ‭Line‬‭=‬‭y = m * x + c‬
‭-‬ ‭Half-plane‬‭= one side of the line;‬‭y <= m * x + c‬
‭-‬ ‭Line segment‬‭= two endpoints‬
‭-‬ ‭Two segments intersect if they have some point in common‬
‭-‬ ‭Proper intersection‬‭: common point is exactly one interior‬‭point of each line‬
‭segment‬
‭-‬ ‭Polygon‬‭= connected region of a plane, bounded by‬‭line segments‬
‭-‬ ‭Edges = its line segments‬
‭-‬ ‭Vertices = endpoints of the edges‬
‭-‬ ‭Circle‬‭= only the boundary (edge)‬
‭-‬ ‭Disk‬‭= boundary + its interior‬

‭Relations‬
‭-‬ ‭Euclidean distance‬




‭-‬ ‭Manhattan distance‬‭(sum of the segments below)‬




‭-‬ ‭Intersection‬‭: set of points that two objects have‬‭in common‬

‭Description size‬
‭-‬ ‭A point, line (segment), circle, rectangle requires‬‭O(1)‬‭storage‬
‭-‬ ‭A simple polygon with‬‭n‬‭vertices requires‬‭O(n)‬‭storage‬




‭2‬

,‭Convex hulls‬
‭ onvex‬ ‭Shape or set if for any two points that are‬‭part of the shape, the connecting line‬
C
‭segment is also part of the shape‬
‭-‬ ‭Circle‬‭is not‬‭convex‬‭, but a‬‭disk‬‭is‬
‭Convex hull‬ ‭Intersection of all convex sets that‬‭contains a subset‬‭S‬‭of the plane (set of points,‬
‭rectangle, simple polygon); Smallest set that contains‬‭S‬

‭Convex hull problem‬‭: give algorithm that computes‬‭the convex hull of any given set of‬‭n‬‭points‬
‭-‬ ‭Input has 2n‬‭coordinates and thus‬‭O(n)‬‭size‬
‭-‬ ‭Output has at least 4 and at most 2n coordinates, and thus between‬‭O(1)‬‭and‬‭O(n)‬‭size‬
‭-‬ ‭Useful insights (that you have to‬‭prove!‬‭):‬
‭-‬ ‭Vertices of the convex are always points from the input‬
‭-‬ ‭Supporting line of any convex hull‬‭edge‬‭has all input‬‭points to one side‬
‭-‬ ‭Based on this you can create a‬‭slow‬‭algorithm that‬‭goes through all pairs‬
‭of points and adds it to result if all other points lie on one side of the line‬
‭through the pair‬
‭-‬ ‭Better algorithm: sort the points from left to right (by‬‭x‬‭coordinate), then iterate‬
‭-‬ ‭Idea: first compute‬‭upper boundary‬‭, then‬‭lower boundary‬‭is symmetric‬
‭1.‬ ‭Add two leftmost points to result‬
‭2.‬ ‭Keep adding next point until entire list is processed:‬
‭a.‬ ‭If this is a left turn, remove previous points that shouldn’t be in the hull‬
‭because of this (can go as far back as the first two points!)‬




‭b.‬ ‭If this is a right turn, continue‬
‭ .‬ D
3 ‭ o similar in the other direction (to compute‬‭bottom‬‭boundary‬‭)‬
‭4.‬ ‭Concatenate two lists‬
‭-‬ ‭Analysis:‬‭O(n log n)‬‭to sort and for each point after‬‭the first three, there can be‬
‭O(1 + k)‬‭steps to add it to the hull and remove previous‬‭points with‬‭k <= n‬‭, so‬
‭you end up with‬‭O(n log n) + O(n‬‭2‭)‬ ‬‭=‬‭O(n‬‭2‬‭)‬
‭-‬ ‭BUT, each point can be removed only once from the upper hull, so‬
‭actually, we have:‬




‭-‬ ‭Hence,‬‭O(n log n) + O(n)‬‭=‬‭O(n log n)‬‭, which is optimal‬

‭Convex hulls in:‬
‭-‬ ‭3D: vertices (0 dim.), edges (1 dim.) and facets (2 dim.), and 3 dim. interior‬
‭-‬ ‭4D: vertices (0 dim.), edges (1 dim.) 2-facets (2 dim.) and 3-facets (3 dim.), and 4 dim.‬
‭interior‬
‭-‬ ‭Its boundary can have‬‭Θ(n‬‭2‬‭)‬‭facets in worst case‬


‭3‬

, ‭Map overlay‬
‭GIS‬‭Geographic Information System‬
‭-‬ ‭Data is stored in separate layers‬
‭-‬ ‭Each layer stores geometric info about e.g. roads, land cover, boundaries, habitats‬
‭Map overlay‬‭Combination of two (or more) map layers‬
‭-‬ ‭Answer queries such as total length of roads through forests etc.‬


‭Line segment intersection‬
‭ utput-sensitive‬‭If output is large, it is fine to‬‭spend a lot of time, but if the output is small, the‬
O
‭algorithm is fast‬
‭-‬ ‭Input-sensitive‬‭applies to the running time of any‬‭algorithm (depends on‬‭n‬‭)‬

‭Line intersection problem‬‭: given‬‭n‬‭line segments,‬‭find their intersection points‬
‭-‬ ‭Naive approach: loop over every pair of segments and report their intersections‬
‭-‬ ‭If every line intersects every other line, this is optimal, since there would be‬‭n‭2‬ ‬
‭intersections to report, and algorithm runs in‬‭O(n‬‭2‬‭)‬‭(and every algorithm needs at‬
‭least as much time as it takes to report all the answers)‬
‭-‬ ‭However, in the map overlay problem, you can expect that not every line‬
‭segment intersects a‬‭lot‬‭of line segments from the‬‭other map layer‬
‭-‬ ‭Typically, can expect‬‭k = O(n)‬‭intersections, then‬‭you can find all‬
‭intersections in‬‭O(n log n) + k‬‭time (and‬‭k‬‭falls‬‭away)‬

‭Overlapping pairs‬
‭-‬ ‭Given set of intervals on a line, find all partly overlapping pairs‬
‭-‬ ‭Sort endpoints and iterate left to right, maintaining currently intersected intervals in BST‬
‭-‬ ‭Whenever you come across a start endpoint, report all other segments in the‬
‭BST, and then insert the segment of this endpoint‬
‭-‬ ‭Running time‬‭O(n log n + k)‬‭, where‬‭k‬‭could be at least‬‭n‬‭2‭/‬ 4‬‭so quadratic worst‬
‭-‬ ‭This is‬‭output-sensitive‬‭for 1D, but not for 2D, because‬‭it’s possible for there to be a‬
‭bunch of vertical line segments that do not intersect, thus should be able to run in‬‭O(n‬
‭log n)‬‭, whereas the 1D algorithm would run in‬‭O(n‬‭log n + n‬‭2‭)‬ ‬

‭ lane sweep technique‬ ‭Imaginary horizontal line passing‬‭over the plane from top to‬
P
‭bottom, solving the problem as it moves‬
‭-‬ ‭Events‬‭: places where the line stops and algorithm‬‭computes some positions‬
‭-‬ ‭Status‬‭: storage of relevant situations at current‬‭position of the sweep line‬
‭-‬ ‭At every point, everything above the sweep line is already done‬
‭-‬ ‭General guide:‬
‭1.‬ ‭Define status‬
‭2.‬ ‭Choose status structure and event queue‬
‭3.‬ ‭Figure out how events must be handled (use sketches!)‬
‭4.‬ ‭Analyze number of events and how much time each event takes‬
‭5.‬ ‭Deal with degenerate cases, incorporating them carefully‬




‭4‬

Voordelen van het kopen van samenvattingen bij Stuvia op een rij:

Verzekerd van kwaliteit door reviews

Verzekerd van kwaliteit door reviews

Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!

Snel en makkelijk kopen

Snel en makkelijk kopen

Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.

Focus op de essentie

Focus op de essentie

Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper Suniht. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €9,99. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 52355 samenvattingen verkocht

Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen

Start met verkopen
€9,99
  • (0)
In winkelwagen
Toegevoegd