What is geodata? Give examples.

Geodata is data with spacial reference to the earth (and technically not in reference to other planets). That spacial reference could be direct (with coordinate systems) or indirect (reference to a well-established spatial object, e.g. a city, Brandenburger Tor, etc.).

Examples are:

Maps and plans

surveing data (building ground plans, supply lines)

remote sensing data (satellite images, radar data, earth gravity measurements)

secondary products of remote sensing data (digital terrain models, 3D city models)

navigational data

sensor data (rain radar, water level)

A lot of data is geodata. Music would be an example of non-geodata. Or bank data.

What is a GIS?

A GIS (geographical information system) is a computer-based system for

input and update

management and modelling (putting the data in tables via UML (unified modeling language))

simulation and analyzation (buffer analysis, flowdirection analysis…)

presentation and output

of geodata (functional components).

GIS does not equal the GIS software (ArcGIS, QGIS).

The structural components of a GIS are:

hardware (PC, storage)

software (e.g. ArcGIS, QGIS)

data (the most valuable + longest life span!)

user

A GIS links thematic information with geometric data.

What are some types of GIS?

Land information systems (LIS)

system for legal foundation and documentation, e.g. cadastral map, city base maps

Network Information Systems (NIS)

system for mapping operating resources, such as gas, water, energy, telecommunication

Spatial Information Systems (SIS)

tool for planning and development, e.g. regional land use plan

Environmental Information Systems (EIS)

environmental impact assessment

Application Specialized Information Systems (AIS)

tool for navigation, transport managment

How does Modeling in GIS work?

In a GIS, abstraction is required to model the real world. Our model represents the real world in a specific way, whatever the application is. For example, if we want to know more about the forests in our area, we would map the forests and not necessarily all power supply lines, even if they’re also there.

So, in order to model the real world, the application and the phenomena that needs modeling in order to fulfill that appllication must be chosen.

Then, the spatial data model must be chosen (raster/vector) to represent the data in a conceptual model.

What is geoinformatics?

Goinformatics is the science that “deals with” geodata. It is a bridge between computer sciences and geo sciences.

What is the 4-layer-model in a GIS?

External view: How the GIS is presented to the user (interface, system environment, etc.)

Conceptual view: Thematic, geometric and topological modelling of a section of the real world

Logical view: Representation of the models in data structures

Internal view: Physical data storage and management

In which ways can the world be viewed (to create a spatial data model?)?

Discrete objects: well-defined objects (points, lines, or polygones), “can be counted”, are usually instances of some category (e.g. trees, buildings, …) represented in vector data, can usually be described by attributes

Continuous fields: data has no boundaries and “overlaps” the surface entirely, where every point is measurale and has a different value (e.g. temperature, air pressure, precipitation, terrain, soil types). Variations can be smooth or sudden; can also be defined along lines (traffic on a road, pollution in a river). There are different kinds of continuous fields:

scalar fields (only one variable)

vector fields (two or more variables; wind strength and direction!)

What are some difficulties for geographic modelling?

the world is dynamic and changes eventually - how do we represent change over time? (Areas might change to points if forest is cut down or changes naturally)

how to model different phenomena - i.e. roads as polygons or lines? -> depends on the context/appilcation; but many real-world features do not fit into the avaiable categories (points, lines, polygons)

scale (small-scale: roads as lines. bigger scale: roads as polygons. But at what scale does a “city area” become different buildings (represented as individual polygons)?

What does conceptual modeling consist of?

thematic modeling (identify and group similar features with the same properties (i.e. all roads are one entity, all buildings etc.)) -> in the field of GIS, typically grouping by thematic layer principle or object class principle

geometric modeling (putting features into a specific geometry, i.e. vector or raster)

topological modeling

What is the

1) Thematic Layer principle

2) Object class principle?

Both are methods used in thematic modeling, so grouping similar features together in a specific way, either by

1) thematic layer principle: each theme is modeled in its own layer (i.e. trees in one layer, houses in one layer, streets in one layer) and the geographical information system consists of a number of layers that can be activated/deactivated; to then solve a specific problem, layers can be selected, combined and analyzed together (overlays, buffer, intersecting etc.). That principle is not very flexible as features HAVE to fit in the definition of the layer

2) (hierarchical) object class principle: comparable with object-oriented programming; world consists of objects that are instances of classes (grouping by classes) -> classes can be hierachically organized (+ have relations to other classes), subclasses inherit properties of parent class -> more flexible than thematic layer principle

What are modeling languages for thematic modeling?

Entity-Relationship-Model (ER)

Nijsen Information Analysis Method (NIAM)

Object Modeling Technique (OMT)

Unified Modeling Language (UML)

What are Geographic Reference Systems? Give some examples.

A Coordinate Reference System (CRS) is necessary to relate the coordinates of an object to the physical model of the real world.

Origin and axes orientation differ between mathematical and geodetic coordinate systems!

There are 2D- and 3D coordinate systems.

A geographic 3D coordinate system looks like this:

Points with equal latitude form a line called parallel, points of the same longitude form a meridian line.

There are “concentional” geographic reference systems, such as WGS84, and projected coordinate systems, such as UTM or Gauss-Krüger.

Projected coordinate systems project the earth models’ surface onto a flat map using a cylinder, a cone or a plane.

What kind of projections can be used for projecting the earths surface? Give examples.

equal area projection (sinosoidal projection)

conformal projection (mercator projection)

Explain the concept of point set models using the words

interior

boundary

closure

exterior

A point set consists of a lot of points. They can be inside the point set (interior), meaning the points on the neighborhood of a point are also inside the point set.

Or they can be on the boundary of a point set, meaning the neighboring points are not completely inside the point set.

Or they can be both, which is the closure of a point set.

Everything not inside the closure is the exterior of a point set.

Compare the Vector Model with the Raster Model.

What is Tomlin’s Model for Geographical Analysis?

Operations compute from one or several geo data layers a new layer

model typically used for raster data

The operations:

local: combine values at the same location from one or many layers (+, -, /, sin, boolean)

focal: value of a raster cell is determined by combining values from the (defined) local neighborhood (e.g. mean value, minimum, flow accumulation)

zonal: Summarize data values in some way that fall within given zones (mean values in a specific zone)

zonal:

What is the difference between accuracy and resolution?

A raster model with more resolution is not always more accurate, just “more defined”. For different purposes, the resolution may have to be higher or is fine when lower.

Describe the Raster Model.

Describe the Vector Model.

How do you initialize a class x in python?

class x:

def __init_ (self, y, z):

self.y = y

self.z = z

What is Geopandas? Give some examples for functions.

Geopandas is an open-source python library designed to work with geospatial data. It’s based on the Pandas library and uses the DataFrame as well, just with an extra column for the geometry.

Functions are for example:

spatial joins

coordinate transformations

geometric manipulations such as buffers, centroids…

plotting geospatial data

How do you start using a library in python?

import library

How do you visualiza a dataframe with geopandas?

df.plot() OR

df.explore() <- shows dataframe on a global Earth’s map

How do you filter geodataframes, for example if we only want to have districts with a max population of 1000 inhabitants?

mask = berlin_district[“inhabitants”] <= 1000

berlindistrictselected = berlin_district.loc[mask]

How do you sort geodataframes? Example: Sort geodataframe by column ‘hello’, ascending

geodataframe.sort_values(by=’hello’, ascending=True)

What kind of ellipsoids can be used for determining earth’s coordinates?

Geocentric ellipsoid: WGS84, is determined by satellite orbital data and is considered more accurate for fitting the entire surface of the earth than for a specific region. the polar axis is defined by the rotational axis of the earth, the center of the ellipsoid is the center of the mass.

Regional ellipsoid: good for regions & not for the whole earth. Are in general not geocentric but parallel to the rotational axis. Example: Krassowski ellipsoid (for Eurasia, used in the eastern block).

classical ellipsoid: neither geocentric nor parallel to the rotational axis. Defined by local measurements. Example: Bessel ellipsoid (reference ellipsoid for europe from 1841).

What is the geodetic datum?

A datum describes the position and orientation of a conventional reference system to a global geocentric system, it is a reference point or surface against which position measurements are made, it‘s a set of data which contains:

• the position and

• the dimension of the reference ellipsoid with respect to the Geoid.

What is latitude and longitude?

What is shapely?

shapely is a python library dedicated to the manipulation of geometric forms, such as points (Point or MultiPoint), lines (LineString or MultiLineString), and polygons (Polygon or Multipolygon) as well as the collections of those.

How do you determine whether a line is within a polygon using shapely?

shapely.within(line,polygon) -> is line within polygon? OR

shapely.contains(polygon,line) -> does polygion contain line?

What are some operations that can be used with the shapely library?

crosses: shapely.crosses(line1,line2) -> do line1 and line2 cross each other?

contains: shapely.contains(polygon, line) -> does polygon contain line?

within: shapely.within(line1, polygon -> is line1 within polygon?

intersection: shapely.intersection(polygon1, polygon2) -> intersection between polygon1 and polygon2 (everything that is there in both polygons)

union: shapely.union(polygon1, polygon2) -> union between polygon1 and polygon2

difference: shapely.difference(polygon1, polygon2) -> polygon1 - polygon2

What is the basic building block in a) Raster data and b) Vector data?

For Raster data, the basic building block is the individual cell, while the point itself (coordinate pair) is the basic building block in vector data.

How is the shape of an entity described in a) Raster data and b) vector data?

a) Raster data: the shape is described by a group of cells

b) Vector data: the shape is described by coordinates (lines & areas: a series of connected points who all consist of coordinate pairs)

How can continuos fields be modelled in vector & raster data?

Raster data is widely used for continuos fields, as the value of each cell represents a specific value (e.g. temperature, precipitation etc.).

That is not possible for vector data. If we want to display continuous fields in vector data, we can use isolines in which every line represents a specific value (often used for elevation data)

How can you merge geometries by a certain row with geopandas?

with the dissolve() function (example: berlin_districts.dissole(by=”district")

How do you set a specific row as the geometry in python?

with the geopandas library, you can call the function set_geometry() on a geodataframe and put the row you want to base the geometry on in the brackets.

What is the function for georeferencing raster data?

What types of topology exist?

Connectivity (links between spacial objects, for example line features that meet at common endpoints or street networks)

Adjacency (information about the direct neighbors of spacial objects, for example area fatures that share common boundaries)

Containment (information about the overlap between spacial objects, for example features that occupy the same space)

Why would you store topological data?

Topological data structures enable the explicit modelling of topological relations between spacial objects.

reduces data storage by storing less boundaries because they are shared by neighbors

prevents inconsistencies in the geometric modeling due to closing gaps when editing or digitizing data

allows analysis on topological relations of connectivity, adjacency and containment (shorttest paths, minimum spanning trees etc.)

simplifies the managment of tesselations

What is a 2-Manifold?

A 2-Manifold describes the concept of each point of the surface being surrounded by a 2-dimensional region - except for the points on the boundary, of course. The 2-dimensiojnal region belongs to the surface as well, like in point set modeling.

Not all point sets can be implemented as 2-manifold surfaces - for example objects who touch each other at a single point or line segment like this:

These are special cases where the object is split into several parts.

How do boundary models describe 3D solids?

By their bounding surface(s). The boundary consists of several faces that arer “glued together”. The solid is then either located within and on the boundary (closed set) or only within the boundary (open set).

What are the basic topological elements of a boundary model?

face

edge

vertex/node

What is a boundary model with only straight line segments who form only planar faces called?

This is called a polyhedron. Due to every line segment being a straight line, the data structure is reduced.

The simplest case: Faces are represented as polygons (sequence of coordinate triplets - the corner points!) -> the solid is a collection between those -> the relations between the polygons is not stored -> high redundancy of (corner) point coordinates -> often used in GIS

In this case above, due to not storing the relations between the faces, there is no topological data structure. The geometries are given by a sequence of points (coordinates).

This is called a polygon based boundary model.

How are geometries described without using a topological data structure?

the geometries are given by a sequence of points (coordinates). therefore, a lot of points are stored in several geometries (redundancy) which consists in a higher storage cost and possible inaccuracies in topological relations (gaps/overlaps, especially when changing the geometry without wanting to change the topology).

What Boundary Models exist?

Polygon Based Boundary Model (no topological data structure)

3D Vertex Based Boundary Model

Edge based Boundary Model

How are objects stored in a 3D vertex based boundary model?

Vertices are stored as independent topological entities into the data structure. The vertices are associated with coordinates and polygons are then defined by a sequence of vertices.

The verices are listed in a specfic order, e.g. clockwise, which is good for many algorithms.

What is the edge based boundary model?

Firstly, the vertices are stored seperately like in the 3D vertex model. Then, the edges are stored seperately as well while being desribed with a sequence of vertices. the faces are then not desribed by vertices, but by the edges.

For curved edges, edges can be linked with control points that define the curved geometry.

Edges are not always directed in a clockwise direction (if faces share edges, that is just not always possible.) Therefore, in the winged edge topological data structure, the direction is stored as well. For every edge, the “neighboring” edge and their direction is stored. That results in every edge being linked, so that only the start edge must be stored because the edges are linked and the direction is known.

In a table, show the linked edges and which edges the polygons consists of.

What topological relations are stored in edge based boundary models?

What are the conditions for a valid boundary model?

How do you merge two dataframes using geopandas?

Two dataframes can be merged with the merge() function on a column that is the same in both dataframes. This column must be defined in the function.

This is a possible function: schools_district = schools.merge(sub_districts,on="sub_district")

Dataframes can also be spatially merged (spatial join) with the sjoin()-function.

The 6 arguments of the funtion are:

left_df : the left geodataframe.

right_df : the right geodataframe.

how : the rule to join the geodataframes (left, right, inner).

predicate : spatial predicate (intersects, contains, within, touches, crosses, overlaps).

lsuffix : the suffix to apply to overlapping column names of the left geodataframe.

rsuffix : the suffix to apply to overlapping column names of the right geodataframe.

sjoin_nearest()-function joins two dataframes according to how close they are to one another. with the max_distance-argument, the maximal distance can be determined.

The overlay()-function has several types: intersection, union, identity, difference

Which operations belong to the overlay tool? Sketch examples.

Identity: Includes the area of the input polygons and the areas of the overlay polygons that lie within them. Attribute values are taken from input and overlay polygons

Erase: Includes the part of the input polygons that is not in the area of the overlay polygons. Attribute values are taken over from the input polygon

Union: Includes the union of input and overlay polygons. Attribute values are taken over from the input polygon

Intersect: Includes parts of the input and overlay polygons that exist in both layers.

What is a network?

A network is a collection of interconnecting lines along which there is a flow of data, objects, or materials. They also include topological information (vertices/nodes and edges).

Raster models are not a good choice for this.

Examples: Berlin underground network, street networks

What are some topological problems?

Seven Bridges of Königsberg (walk trough city and cross each bridge exactly once)

the house of Saint Nick

Dog Walking Problem (n dogs, m kids (m >_ n), is there for every dog a candidate for walking? -> solution: vertex-disjoint edge set E with size n

Map Coloring Problem (neighboring regions can not have the same colour!)

Chinese Postman problem (deliver mail following the shortest path -> solved via finding an eularian path!)

What does a graph consist of?

collection of vertices

collection of edges that consist of pairs of vertices

What is the difference between an eularian and a zhamiltonian path?

An eularian path is a path that uses each edge exactly once, while a hamiltonian path is a path that uses each vertex exactly once.

What is a graph called that

has an eularian path

has a cycle that uses each edge exactly once

has a hamiltonian path

can be drawn on a plane without any crossing?

traversable or semi-eularian

Eularian or unicursal

traceable

planar

Are the street networks of North America and Europe connected graphs?

No, because there is no path that connects both of them. They in itself are probably also not connected because of some islands that may or may not have street access.

How can one determine whether a planar graph contains an eularian path or cycle?

It needs to be connected and the degree of all vertices is even except for the start & end vertex for an eularian path (degree: numvber of edges that are incident to the vertex).

For an eularian cycle, the graph must be connected, planar and the degree of all edges must be even, no exceptions.

What is the hamiltonian path/cycle problem?

There is no efficient algorithm known that determines if a graph contains a Hamiltonian path or cycle, yo can just try out all possibilities until you find one.

How can one work with Raster Data using python?

Via using 2D Lists - this is not suitable for big or complex raster data, though.

The lists look like this:

The list consists of several lists (each nlist represents a row! and the elements in the lists represent a cell)

For visualizing raster data, the matplotlib library is useful, especiall the function imshow/(), which visualizes 2D arrays (like raster data) in an image.

Another way of working with raster data is using the rasterio library, which can be used to read and write raster data. For example, with rasterio.open(), a raster file can be read using a dataset reader. Also, the CRS of a raster file can be determined.

Write a little code which assigns the CRS (EPSG: 25832) to the raster file “test” (Data/RSMS_17_2020_01.asc)

import rasterio

from rasterio.crs import CRS

test = rasterio.open(‘Data/RSMS_17_2020_01.asc’, mode='r+')

crs25832 = CRS.from_epsg(25832)

test.crs = crs25832

test.close()

What are 4 subtypes of digital elevation data?

DEM (digital elevation model): contain elevation information, often represented as a raster

DTM (digital terrain model): subset of DEMs containing height information only for the bare ground

DSM (digital surface model): subset of DEMs containing height information including all structures like buildings, trees etc

nDSM (normalized digital surface model): contains relative height information for all structures like buildings, trees etc and can be obtained by subtracting the DTM from the DSM (The nDSM can be obtained as nDSM = DSM - DTM)

Which vertices are predecessors/sucessors of other vertices here?

Vertex a is a predecessor of b if e = (a, b) ∈ E

Vertex a is a successor of b if e = (b, a) ∈ E

5: 5 is a predecessor of 2

2: 2 has 2 predecessors (1,5) and one sucessor (3)

1: 1 has one predecessor (3) and two sucessors (2,4)

4: 4 has one sucessor (3) and one predecessor (1)

3: 3 has two predecessors (2,4) and one sucessor (1)

Write the adjacency matrix, the adjacency list and the incidence matrix for this graph:

How can you represent directed edges?

Matrix:

List:

For weighted graphs, the weight is also stored in the entry of the adjacent vertex (as a pair)

incidence matrix:

The n × m incidence matrix represents the relationships between n vertices and m edges for a graph. Directed edges are depicted by using a - sign in front of incoming edges (predecessors).

How many entries does an

adjacency matrix of an undirected & unweighted graph have?

an adjacency list of each vertex have?

matrix: n², while n is the number of vertices

list: equal to the number of edges the vertex is incident to

How do you search for

neighbor vertices

predecessor vertices

sucessor vertices

in an adjecency list and how long does it take to find all predecessor vertices?

How does an

undirected

directed

object-oriented graph model look like?

How can you check whether a graph has an edge between two specific vertices (x and y)?

One can

use an edge list, where the entire edge list must be looked through

use an adjacency matrix if the graph is undirected (if directed, the matrix only shows the sucessors)

use the adjacency list and search through all lists (if directed) or through the entries for x or y

What are the 2 basic strategies for traversal of graphs? Explain how they work.

Depth first search: recursive algorithm (calls itself again and again) which always marks the current vertex as visited and then looks at the neighbors of that vertex, chose one neighbor, mark the parent and repeat

Breadth first search: iterative algorithm (solves a problem step-wise by repeating a process) that uses a queue to determine which vertex is looked at next

What is the difference between an iterative and a recursive algorithm? Give an example (informal)

A recursive algorithm solves a problem by repeatetly calling itself, while an iterative algorithm solves a problem step-wise by repeating a certain process.

An example for a recursive algorithm is depth first search, while the breadth first search algorithm is an example for an iterative algorithm.

Depth first search:

Breadth first search:

Is the breadth first search or depth first search useful for finding the shortest path from a start vertex to all other vertices of a graph?

The breadth first search provides the shortest path from the root vertex of the spanning tree to all other vertices of the graph, where the weights of all edges are assumed to be the same

Sketch the spanning tree of the graph below, while using

depth firest search

breadth first search

What is the difference between a weighted graph and an unweighted graph?

A weighted graph associates a „cost value“ (weight) with every edge in the graph. An unweighted graph does not have that. In most cases, the weight on the edges is the set of positive rational or integer numbers (if they are negative, we might get some problems, for example in incidence lists, where we set a - in front of edges who are predecessors to the vertex).

The weight of a path is the sum of the weights of the edges that belong to the path.

What types of shortest-path-problems exist?

single-pair (shortest path from one vertex to another vertex)

single-source (shortest path from one vertex to all other vertices; what we learned about!)

single-destination (shortest path from all vertices to one destination vertices; for undirected graphs, this is the same as the single-source-problem; for directed graphs, the edges need to be reversed)

all-pairs (shortest path between all pairs of vertices)

Describe how the algorithm of Dijkstra works (in words). Is it an iterative or recursive algorihtm?

First, set the distance of the start vertex to 0 and all other vertices to ∞ and mark all vertices as not visited - this is the initialization.

The current vertex is the vertex with the shortest distance. Then, every neighbor of the current vertex is looked at and the distances are updated, if the new distance is shorter than the previous one. Then, the current vertex is marked as visited.

This is repeated until the destination vertex (single-pair-problem) or all other vertices (single-source-problem) have been visited.

This is an iterative algorithm, surch as the breadth first search.

With the algorithm of Dijkstra, calculate the shortest path from source vertex S to all other vertices in a graph (in table form, just as we learned in the lecture).

what is the degree of vertex G?

From the following adjacency matrix,

a) draw the graph

b) does an eularian path exist for this graph?

c) compute the shortest path from A to D with the algorihtm of Dijkstra.

C)

With the algorithm of Dijkstra, compute the shortest path from A to all other vertices.

Also, draw the incidence matrix not considering the edge weights as well as the adjacency matrix.

Draw some subgraphs of the graph below.

What is the difference between a connected component and a connected graph?

Can a connected graph have several connected components?

No.

What is the difference between a forest and tree (in graph modeling)?

Give definitions of (minimum) spanning trees & minimum spanning forests.

Describe the algorithm of Kruskal.

The graph must bean undirected, weighted graph.

First, create a forest with no edges from the vertcies of said graph.

Put the edges of the graph as a set/queue Q (a priority queue can be used).

While Q is not empty, remove the edge witht the lowest weight from Q - if the edge connects two different trees, them add it to the forest so that two trees are joined together. Otherwise, discard the edge.

Repeat until Q is empty.

For graphs that are not connected, the algorithm finds the minimal spanning forest.

To find a minimum spanning forest, what conditions must the graph fulfill?

The graph must be undirected and weighted and not connected (several connected components), so that not a minimum spanning tree but a minimum spanning forest is found.

What are the operations that can be used for the priotity queue?

With the following graph, find the minimum spanning tree using the algorithm of Kruskal.

What is the disjoint-set?

Implement a function to check whether a graph contains a Eulerian path or cycle in python.

With what python library is it possible to create a graph and what are the basic operations?

graph_tool

How do you create an undirected graph in python?

graph = gt.Graph(directed=False)

Then add the vertices like this:

vx = graph.add_vertex(len(vertices_gpd))

Describe the following tree with the following words: root, order of tree, interior vertices, leaves, order of the interior vertices, order of the leaf vertices

Is the tree a complete or binary tree?

The vertex without predecessors is called the Root/parent of the tree. All other vertices have exactly one predecessor. The leaves are the vertices that have no sucessors/children. Thwe othwer vertices which are neither root or leaves are called interior vertices. As the order of the vertex, the number of successors of the vertex is desribed. the order of a tree is the largest order of a vertex occurring in a tree.

• Complete tree: every vertex has either 0 or k successor vertices → k is then the order of all interior vertices and of the tree itself. This treee is therefore complete.

• Binary tree: all vertices have order <= 2 (k = 2) (the tree is binary! Because the order of the vertices is <= 2 and the order of the tree is 2.)

Give

the height of the tree

the depth of vertex 4

the depth of vertex 0

height of the vertex 16

level of the vertex 32

Height of the tree: the height of the root - 2 in this case

Depth of vertex 4: number of edges along the path from root to vertex v - 0 in this case

Depth of vertex 0: number of edges along the path from root to vertex v - 2 in this case

Height of the vertex 16: number of edges along the longest path from vertex v to a leaf - so 1 in this case

Level of the vertex 32: the height of the tree minus the depth of that vertex - height of tree = 2, depth of the vertex = 2 so level = 2 - 2 = 0

Construct a binary search tree by inserting the following elements one after the other: 83, 53, 20, 47, 75, 7, 5, 4, 65, 99

How do you find a specific vertex in a binary search tree? Explain.

In the following search tree, how does the tree look if the vertex 53 is deleted?

What is a balanced tree and what is a formula for calculating the height of a binary balanced tree with n vertices?

Due to their maximum logarithmic height, the search time in a binary search tree is O(log n) (where n is the number of elements stored in the search tree)

What are examples for balanced trees (different types) and are they binary or not?

AVL-Tree (Binary tree)

2-3 Tree (no Binary tree)

B-Tree (no Binary tree)

List 3 queries that can be used to find neare3st neighbors using search trees.

Construct a KD-tree with the following point set (you need to number them first!)

Why are queries together with KD-trees, regardless if nearest neighbor, ball or window query, useful if searching for points?

Especially when considering a large KD-tree, a lot of regions can be left out when searching for points. This means that there will be a lot less searching than if the point set was not divided by a KD-tree.

For the KD-tree, draw a window query and compute the result set.

Why are unbalanced search trees worse than balanced search trees?

Hoe do you split a root node, a node when the parent is a 2node and a node when the parent is a 3-node in 2-3 Search trees?

How do you search for a key in a 2-3 search tree?

Last changed6 months ago