Convex hull trick and Li Chao tree
1. Overview Consider the following problem. There are $n$ cities. You want to travel from city $1$ to city $n$ by car. To do this […]
Month: July 2021
Convex Hull construction using Graham’s Scan
In this article we will discuss the problem of constructing a convex hull from a set of points. Consider $N$ points given on a plane, […]
Lattice points inside non-lattice polygon
1. Overview For lattice polygons there is Pick’s formula to enumerate the lattice points inside the polygon. What about polygons with arbitrary vertices? Let’s process […]
Pick’s Theorem – area of lattice polygons
A polygon without self-intersections is called lattice if all its vertices have integer coordinates in some 2D grid. Pick’s theorem provides a way to compute […]
Minkowski sum of convex polygons
1. Definition Consider two sets $A$ and $B$ of points on a plane. Minkowski sum $A + B$ is defined as $\{a + b| a […]
Check if point belongs to the convex polygon in $O(\log N)$
Consider the following problem: you are given a convex polygon with integer vertices and a lot of queries. Each query is a point, for which […]
Finding area of simple polygon in $O(N)$
Let a simple polygon (i.e. without self intersection, not necessarily convex) be given. It is required to calculate its area given its vertices. 1. Method […]
Oriented area of a triangle
Given three points $p_1$, $p_2$ and $p_3$, calculate an oriented (signed) area of a triangle formed by them. The sign of the area is determined […]
Length of the union of segments
Given $n$ segments on a line, each described by a pair of coordinates $(a_{i1}, a_{i2})$. We have to find the length of their union. The […]
Finding common tangents to two circles
Given two circles. It is required to find all their common tangents, i.e. all such lines that touch both circles simultaneously. The described algorithm will […]
Circle-Circle Intersection
You are given two circles on a 2D plane, each one described as coordinates of its center and its radius. Find the points of their […]
Circle-Line Intersection
Given the coordinates of the center of a circle and its radius, and the equation of a line, you’re required to find the points of […]
Finding Intersection of Two Segments
You are given two segments AB and CD, described as pairs of their endpoints. Each segment can be a single point if its endpoints are […]
Check if two segments intersect
You are given two segments $(a, b)$ and $(c, d)$. You have to check if they intersect. Of course, you may find their intersection and […]
Intersection Point of Lines
You are given two lines, described via the equations $a_1 x + b_1 y + c_1 = 0$ and $a_2 x + b_2 y + […]
Finding the equation of a line for a segment
The task is: given the coordinates of the ends of a segment, construct a line passing through it. We assume that the segment is non-degenerate, […]
Basic Geometry
In this article we will consider basic operations on points in Euclidean space which maintains the foundation of the whole analytical geometry. We will consider […]
Integration by Simpson’s formula
We are going to calculate the value of a definite integral $$\int_a ^ b f (x) dx$$ The solution described here was published in one […]
Newton’s method for finding roots
This is an iterative method invented by Isaac Newton around 1664. However, this method is also sometimes called the Raphson method, since Raphson invented the […]
Ternary Search
We are given a function $f(x)$ which is unimodal on an interval $[l, r]$. By unimodal function, we mean one of two behaviors of the […]
