DSA 2 at Technische Universität Graz

Flashcards and summaries for DSA 2 at the Technische Universität Graz

Arrow Arrow

It’s completely free

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

studysmarter schule studium
d

4.5 /5

studysmarter schule studium
d

4.8 /5

Study with flashcards and summaries for the course DSA 2 at the Technische Universität Graz

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

Triangulation of a point set S in the plain is ...

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

Triangulation of a Polygon P is ...

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

Plane Straight-Line Graph is

This was only a preview of our StudySmarter flashcards.
Flascard Icon Flascard Icon

Millions of flashcards created by students

Flascard Icon Flascard Icon

Create your own flashcards as quick as possible

Flascard Icon Flascard Icon

Learning-Assistant with spaced repetition algorithm

Sign up for free!

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

Maximal Plane Straight-Line Graph is

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

How many edges and triangles can a triangulation of a pointset S with n points have?

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

How many edges and triangles can a triangulation of a polygon P with n vertices have?

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

What can triangulations be used for?

This was only a preview of our StudySmarter flashcards.
Flascard Icon Flascard Icon

Millions of flashcards created by students

Flascard Icon Flascard Icon

Create your own flashcards as quick as possible

Flascard Icon Flascard Icon

Learning-Assistant with spaced repetition algorithm

Sign up for free!

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

A triangulation for an n-point set can be constructed in

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

A directed Graph is called ... if it has no loops

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

Simplepath contains ...

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

Length in weighted graphs is  ...

This was only a preview of our StudySmarter flashcards.
Flascard Icon Flascard Icon

Millions of flashcards created by students

Flascard Icon Flascard Icon

Create your own flashcards as quick as possible

Flascard Icon Flascard Icon

Learning-Assistant with spaced repetition algorithm

Sign up for free!

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

An undirected graph is a forest if

Your peers in the course DSA 2 at the Technische Universität Graz create and share summaries, flashcards, study plans and other learning materials with the intelligent StudySmarter learning app.

Get started now!

Flashcard Flashcard

Exemplary flashcards for DSA 2 at the Technische Universität Graz on StudySmarter:

DSA 2

Triangulation of a point set S in the plain is ...

a partition of the convex hull of it into interior-disjoint triangles, whose edges are segments spanned by the points of S.
Also no point of S lies inside a segment or a triangle.

DSA 2

Triangulation of a Polygon P is ...

the maximal plane straight-line graph on S inside P

DSA 2

Plane Straight-Line Graph is

a set of points in the plain and the set of edges spend by this points, such that no two edges cross in their interior

DSA 2

Maximal Plane Straight-Line Graph is

one where we can't add any edge without crossing another edge.


-> We can obtain a Maximal Plane Straight-Line Graph by adding edges, that are not crossing the other edges, as long as possible (the result is always a TRIANGULATION)

DSA 2

How many edges and triangles can a triangulation of a pointset S with n points have?

e = 3n−3−h   edges 

t = 2n−2−h    triangles
h -> extreme points

DSA 2

How many edges and triangles can a triangulation of a polygon P with n vertices have?

                                                e = 2n−3   edges 

                                             t = n−2     triangles 

-> The number of edges and triangles is linear in the number of vertices 

DSA 2

What can triangulations be used for?

  • modelling surfaces
  • triangular networks in cartography
  • 3D modeling
  • Computer Graphics
  • simulation of fluid flows
  • proving time bounds
  • finding shortest path inside a polygon
  • combinatorics
  • ...

DSA 2

A triangulation for an n-point set can be constructed in

 O(n log n) time

             Θ(n) space

DSA 2

A directed Graph is called ... if it has no loops

simple

DSA 2

Simplepath contains ...

every vertex in V at most once 

DSA 2

Length in weighted graphs is  ...

the sum of the edge weights

DSA 2

An undirected graph is a forest if

if it is acyclic

Sign up for free to see all flashcards and summaries for DSA 2 at the Technische Universität Graz

Singup Image Singup Image
Wave

Other courses from your degree program

For your degree program DSA 2 at the Technische Universität Graz there are already many courses on StudySmarter, waiting for you to join them. Get access to flashcards, summaries, and much more.

Back to Technische Universität Graz overview page

Bürgerliches Recht und Unternehmensrecht

CON (Networks)

Ducci 2 at

Karlsruher Institut für Technologie

DSD at

Karlsruher Institut für Technologie

DS at

TU München

2.1 at

Hochschule für Technik und Wirtschaft des Saarlandes

P&D 2 at

Universität Innsbruck

Similar courses from other universities

Check out courses similar to DSA 2 at other universities

Back to Technische Universität Graz overview page

What is StudySmarter?

What is StudySmarter?

StudySmarter is an intelligent learning tool for students. With StudySmarter you can easily and efficiently create flashcards, summaries, mind maps, study plans and more. Create your own flashcards e.g. for DSA 2 at the Technische Universität Graz or access thousands of learning materials created by your fellow students. Whether at your own university or at other universities. Hundreds of thousands of students use StudySmarter to efficiently prepare for their exams. Available on the Web, Android & iOS. It’s completely free.

Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards
Awards

Best EdTech Startup in Europe

Awards
Awards

EUROPEAN YOUTH AWARD IN SMART LEARNING

Awards
Awards

BEST EDTECH STARTUP IN GERMANY

Awards
X

StudySmarter - The study app for students

StudySmarter

4.5 Stars 1100 Rating
Start now!
X

Good grades at university? No problem with StudySmarter!

89% of StudySmarter users achieve better grades at university.

50 Mio Flashcards & Summaries
Create your own content with Smart Tools
Individual Learning-Plan

Learn with over 1 million users on StudySmarter.

Already registered? Just go to Login