Dijkstra Algorithm
You are given a directed or undirected weighted graph with $n$ vertices and $m$ edges. The weights of all edges are non-negative. You are also […]
Month: August 2021
Strong Orientation
A strong orientation of an undirected graph is an assignment of a direction to each edge that makes it a strongly connected graph. That is, after the orientation we should […]
Finding strongly connected components – Building condensation graph
1. Definitions You are given a directed graph $G$ with vertices $V$ and edges $E$. It is possible that there are loops and multiple edges. […]
Finding articulation points in a graph in $O(N+M)$
We are given an undirected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes […]
Finding Bridges Online
1. Overview We are given an undirected graph. A bridge is an edge whose removal makes the graph disconnected (or, more precisely, increases the number […]
Finding bridges in a graph in $O(N+M)$
We are given an undirected graph. A bridge is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the […]
Search for connected components in a graph
Given an undirected graph $G$ with $n$ nodes and $m$ edges. We are required to find in it all the connected components, i.e, several groups […]
Depth First Search
Depth First Search is one of the main graph algorithms. Depth First Search finds the lexicographical first path in the graph from a source vertex […]
Breadth-first search
Breadth first search is one of the basic and essential searching algorithms on graphs. As a result of how the algorithm works, the path found […]
Half-plane intersection – S&I Algorithm in O(Nlog N)
In this article we will discuss the problem of computing the intersection of a set of half-planes. Such an intersection can be conveniently represented as […]
Vertical decomposition
1. Overview Vertical decomposition is a powerful technique used in various geometry problems. The general idea is to cut the plane into several vertical stripes […]
Delaunay triangulation and Voronoi diagram
1. Overview Consider a set $\{p_i\}$ of points on the plane. A Voronoi diagram $V(\{p_i\})$ of $\{p_i\}$ is a partition of the plane into $n$ regions $V_i$, […]
Finding the nearest pair of points
1. Problem statement Given $n$ points on the plane. Each point $p_i$ is defined by its coordinates $(x_i,y_i)$. It is required to find among them […]
Point location in O(log n)
Consider the following problem: you are given a planar subdivision without no vertices of degree one and zero, and a lot of queries. Each query is a […]
Search for a pair of intersecting segments
Given $n$ line segments on the plane. It is required to check whether at least two of them intersect with each other. If the answer […]
