Introduction To
Geometric Algorithms are designed to solve Geometric Problems. They requires in-depth knowledge of different mathematical subjects like combinatorics, topology, algebra, differential geometry etc.
These algorithms has the following characteristics;
1. Relevant - they solve significant geometric problems for real world applications
2. Correct - they give accurate solutions for the problems
3. Robust - they tolerate small numerical errors and avoid overflow within constraints
4. Efficient - they are fast in practice for typical applications, both small and large
5. Conservative - they use few resources, such as storage space
6. Maintainable - they are straightforward to implement and troubleshoot
7. Elegant - one can understand why they work, which gives confidence in their use.
Course Structure
Lines
- How to check if two given line segments intersect?
- Given n line segments, find if any two segments intersect
- Klee’s Algorithm (Length Of Union Of Segments of a line)
- Count maximum points on same line
- Find an Integer point on a line segment with given two ends
- Minimum lines to cover all points
- Minimum block jumps to reach destination
- Program for Point of Intersection of Two Lines
- Represent a given set of points by the best possible straight line
- Program to find line passing through 2 Points
- Reflection of a point about a line in C++
- Find points at a given distance on a line of given slope
- Number of ordered points pair satisfying line equation
- Check if a line passes through the origin
- Count of different straight lines with total n points with m collinear
- Number of horizontal or vertical line segments to connect 3 points
- Program to find the mid-point of a line
- Section formula (Point that divides a line in given ratio)
- Sum of Manhattan distances between all pairs of points
- Minimum number of points to be removed to get remaining points on one side of axis
- Program to find slope of a line
- Maximum integral co-ordinates with non-integer distances
- Direction of a Point from a Line Segment
- Find intersection point of lines inside a section
- Program to check if three points are collinear
Triangle
- Check whether a given point lies inside a triangle or not
- Program to find area of a triangle
- Count Integral points inside a Triangle
- Classify a triangle
- Maximum height when coins are arranged in a triangle
- Find all sides of a right angled triangle from given hypotenuse and area | Set 1
- Maximum number of 2×2 squares that can be fit inside a right isosceles triangle
- Check if right triangle possible from given area and hypotenuse
- Triangle with no point inside
- Find all angles of a given triangle
- Program to find Circumcenter of a Triangle
- Number of Triangles that can be formed given a set of lines in Euclidean Plane
- Triangular Matchstick Number
- Number of jump required of given length to reach a point of form (d, 0) from origin in 2D plane
- Program to calculate area of Circumcircle of an Equilateral Triangle
- Check whether triangle is valid or not if sides are given
- Program to find third side of triangle using law of cosines
- Find the dimensions of Right angled triangle
- Program to calculate area and perimeter of equilateral triangle
- Count of acute, obtuse and right triangles with given sides
- Minimum height of a triangle with given base and area
- Maximum number of squares that can fit in a right angle isosceles triangle
Rectangle | Square | Circle
- Find if two rectangles overlap
- Check if four segments form a rectangle
- Check whether a given point lies inside a rectangle or not
- Minimum Perimeter of n blocks
- Number of rectangles in N*M grid
- Find Corners of Rectangle using mid points
- Coordinates of rectangle with given points lie inside
- Total area of two overlapping rectangles
- Program for Area And Perimeter Of Rectangle
- Program to find Perimeter / Circumference of Square and Rectangle
- Program for Area Of Square
- Number of unique rectangles formed using N unit squares
- How to check if given four points form a square
- Program to find area of a circle
- Circle and Lattice Points
- Queries on count of points lie inside a circle
- Check whether a point exists in circle sector or not.
- Pizza cut problem (Or Circle Division by Lines)
- Minimum revolutions to move center of a circle to a target
- Angular Sweep (Maximum points that can be enclosed in a circle of given radius)
- Check if a line touches or intersects a circle
- Check if a given circle lies completely inside the ring formed by two concentric circles
- Area of a Circumscribed Circle of a Square
- Area of square Circumscribed by Circle
- Count ways to divide circle using N non-intersecting chords
- Find the center of the circle using endpoints of diameter
- Program to find area of a Circular Segment
- Program to find smallest difference of angles of two parts of a given circle
- Arc length from given Angle
- Area of a Circular Sector
- Find minimum radius such that atleast k point lie inside the circle
- Program to find Circumference of a Circle
- Check whether given circle resides in boundary maintained by two other circles
- Check if two given circles touch or intersect each other
- Count of obtuse angles in a circle with ‘k’ equidistant points between 2 given points
3D Objects
- Find the perimeter of a cylinder
- Find the Surface area of a 3D figure
- Program for distance between two points on earth
- Calculate Volume of Dodecahedron
- Program for Volume and Surface area of Frustum of Cone
- Program to calculate volume of Octahedron
- Program for Surface Area of Octahedron
- Program to calculate area and volume of a Tetrahedron
- Program to calculate Volume and Surface area of Hemisphere
- Maximize volume of cuboid with given sum of sides
- Program to calculate volume of Ellipsoid
- Program for volume of Pyramid
- Calculate volume and surface area of a cone
- Calculate Volume and Surface area Of Sphere
- Program for Volume and Surface Area of Cuboid
- Program for Volume and Surface Area of Cube
- Pythagorean Quadruple
- LS3/NS3 sphere generation algorithm and its implementation
Quadrilaterals
- Number of parallelograms when n horizontal parallel lines intersect m vertical parallellines
- Program for Circumference of a Parallelogram
- Program to calculate area and perimeter of Trapezium
- Program to find area of a Trapezoid
- Find all possible coordinates of parallelogram
- Maximum area of quadrilateral
- Check whether four points make a parallelogram
- Find the Missing Point of Parallelogram
Polygon & Convex Hull
- How to check if a given point lies inside or outside a polygon?
- Minimum Cost Polygon Triangulation
- Area of a polygon with given n ordered vertices
- Tangents between two Convex Polygons
- Regular polygon using only 1s in a binary numbered circle
- Find number of diagonals in n sided convex polygon
- Convex Hull | Set 1 (Jarvis’s Algorithm or Wrapping)
- Convex Hull | Set 2 (Graham Scan)
- Quickhull Algorithm for Convex Hull
- Convex Hull using Divide and Conquer Algorithm
- Dynamic Convex hull | Adding Points to an Existing Convex Hull
- Deleting points from Convex Hull
- Number of Pentagons and Hexagons on a Football
- Program to calculate area of Enneagon
- Program to calculate Area Of Octagon
- Area of a Hexagon
- Minimum area of a Polygon with three points given
Misc
- Find Simple Closed Path for a given set of points
- Orientation of 3 ordered points
- Number of Integral Points between Two Points
- Closest Pair of Points using Divide and Conquer algorithm
- Closest Pair of Points | O(nlogn) Implementation
- Optimum location of point to minimize total distance
- n’th Pentagonal Number
- Find perimeter of shapes formed with 1s in binary matrix
- Count of parallelograms in a plane
- Minimum distance to travel to cover all intervals
- Rotation of a point about another point in C++
- Draw geometric shapes on images using OpenCV
- Finding the vertex, focus and directrix of a parabola
- Program to check if water tank overflows when n solid balls are dipped in the water tank
- Program to check if tank will overflow, underflow or filled in given time
- Find if it’s possible to rotate the page by an angle or not.
- Equable Shapes
- Find mirror image of a point in 2-D plane