Unit IV- Geometric and Optimization Algorithms-

Geometric algorithms- Introduction, range searching-

Geometric algorithms are a branch of algorithms that deal with geometric objects like points,
lines, polygons, circles, and rectangles. They are studied under Computational Geometry.

 Purpose: To solve geometric problems efficiently.

 Applications:
o Computer graphics (rendering, visibility, ray tracing)
o Robotics (motion planning, obstacle avoidance)
o GIS (geographical information systems)
o CAD (computer-aided design)
o Pattern recognition
o VLSI design

Range Searching
Range searching is the problem of preprocessing a set of points so that we can quickly
answer queries of the type:

"Which points lie inside a given range (region)?"

 Input: A set of n points in the plane.

 Query: A geometric range (e.g., rectangle, circle, half-plane).
 Output: All points inside the range.

Types of Range Searching

Here are the three types of range searching illustrated ✅

1. Orthogonal Range Searching → Query is an axis-aligned rectangle (green dashed

box).
2. Simplex Range Searching → Query is a triangle (or convex polygon) (magenta
dashed triangle).
3. Half-space Range Searching → Query is a half-plane defined by a line (red dashed
line, shaded region is valid).

fig -simplex range

searching
Techniques / Data Structures

 Range Trees – Balanced binary trees that store points for efficient searching.
 Segment Trees – Useful when ranges are intervals.
 k-d Trees (k-dimensional trees) – Space-partitioning data structure for efficient
range and nearest-neighbor queries.
 Quad Trees – Divide the plane into quadrants recursively.

4. Applications

 GIS → find points of interest in a region.

 Computer Graphics → collision detection, ray tracing.
 Machine Learning → nearest neighbor search, anomaly detection.
 Robotics / AR / Autonomous Vehicles → spatial queries in real-time.

fig range searching

Convex Hull – Introduction
 The convex hull of a set of points is the smallest convex polygon that contains all the
points.
 Imagine stretching a rubber band around all the points — when released, it will
enclose the convex hull.

Properties
1. It is always a convex polygon.
2. All given points lie inside or on the hull.
3. Vertices of the convex hull are a subset of the given points.

Algorithms for Convex Hull

1. Gift Wrapping (Jarvis March) – O(nh) where h = number of hull vertices.
2. Graham’s Scan – O(n log n).
3. Divide and Conquer – O(n log n).
4. QuickHull – Average O(n log n), worst O(n²).

Applications
 Computer graphics (collision detection, shape analysis).
 Robotics (navigation, path planning).
 GIS (bounding geographical regions).
 Machine learning (support vector machines).
  segment intersections-🔹 1. Definition

 Problem: Given a set S of line segments in the plane, determine whether they
intersect, and if so, find all intersection points.
 Input: Line segments defined by their endpoints.
 Output:
o Decision problem: Do any two segments intersect?
o Reporting problem: Find all intersection points

OR

Each segment can be a single point if its endpoints are the same. You have to find
the intersection of these segments, which can be empty (if the segments don't
intersect), a single point or a segment (if the given segments overlap).

Segment Intersection – Notes

1. Introduction
 One of the fundamental problems in computational geometry.
 Problem: Given n line segments in a plane, report all their intersection points.
 Applications:
o Computer Graphics → ray shooting, rendering.
o Robotics/Motion Planning → collision detection, path planning.
 o GIS (Geographic Information Systems) → overlay of maps, road networks.
o CAD/CSG (Solid Modeling) → Boolean operations on shapes.

2. Basic Definitions
 Line Segment: Defined by two endpoints (x1,y1)(x_1, y_1)(x1​,y1​), (x2,y2)(x_2,
y_2)(x2​,y2​).
 Intersection Point: A point that lies on both segments.
 General Position Assumptions (for simplicity):
1. No two endpoints have same coordinates.
2. No vertical/horizontal segments.
3. No endpoint lies on another segment.
4. No three collinear segments.

3. Complexity of the Problem

 Maximum intersections: O(n²) (every segment intersects every other).
 Brute Force: Check all pairs → O(n²) time.
 Need an output-sensitive algorithm (time depends on n and m, number of
intersections).

4. Plane Sweep Algorithm

 Key Idea: Sweep a vertical line left to right across the plane.
 Maintain dynamic set of active segments (those crossing the sweep line).
 Event Points:
1. Segment left endpoints (insert).
2. Segment right endpoints (delete).
3. Intersection points (report + swap order).

Data Structures Used

 Event Queue (Priority Queue): Stores future events ordered by x-coordinate.

 Sweep-Line Status (Balanced BST like Red-Black Tree): Maintains segments
intersecting sweep line, ordered top-to-bottom.

Steps

1. Insert all endpoints into event queue.

2. Process events one by one (left → right):
o Left Endpoint: Insert segment in sweep-line; check neighbors for
intersections.
o Right Endpoint: Remove segment; check if its neighbors now intersect.
o Intersection Point: Report it, swap order of segments, check new neighbors.

5. Complexity
  O((n + m) log n)
o n = number of segments
o m = number of intersections reported

6. Advantages
 Efficient for sparse intersections (when m ≪ n²).
 Output-sensitive (depends on actual intersections).

7. Applications
 GIS: Overlaying road maps & political boundaries.
 CAD/CSG: Constructive solid geometry operations.
 Robotics: Collision detection.
 Computer Graphics: Ray-object intersection.

Closest Pair of Points – Notes

1. Introduction
 Problem: Given a set PPP of n points in the plane, find the pair of points with the
minimum Euclidean distance.
 Applications:
o Pattern recognition
o Image processing
o Clustering and classification
o Geographic Information Systems (GIS)
o Nearest neighbor search

2. Distance Formula
Distance between two points: d(p1​,p2​)= underoot square (x1​−x2​)2+(y1​−y2​)2​

3. Brute Force Method

 Compare every pair of points.
 Time Complexity: O(n2)
 Not efficient for large datasets.

4. Efficient Algorithm – Divide & Conquer

 Similar to Merge Sort idea.
 Steps:
1. Sort all points by x-coordinate.
2. Divide into two halves (left and right).
3. Recursively compute closest pair in each half.
 4. Combine step: Check if there exists a closer pair across the boundary strip.
 Only need to check at most 6 neighboring points in strip (proved by
geometry).
5. Return the minimum of left, right, and strip distances.

5. Complexity
 Sorting = O(n log n).
 Divide & Conquer recurrence: T(n)=2T(n/2)+O(n)⟹O(nlogn)

 Final Time Complexity: O(n log n)

6. Variants
 Higher dimensions: Can extend to 3D, but complexity increases.
 Dynamic closest pair: When points are inserted/deleted → needs advanced data
structures (kd-trees).

7. Example
 Points: (0,0),(3,4),(7,7),(1,1)
 Distances:
o d((0,0),(1,1)) =square root 2
o d((3,4),(7,7)) = 5
o Closest pair = (0,0)(1,1)

Optimization Algorithms- Introduction-

Optimization Algorithms – Introduction

1. What is Optimization?
 Optimization = process of finding the best solution from a set of feasible solutions.
 Goal: Minimize or maximize an objective function subject to given constraints.

General Form:
Optimize f(x)subject to x ∈ S

 f(x) = objective function

 S = feasible solution space

2. Types of Optimization Problems

1. Linear vs. Nonlinear
o Linear: Objective function & constraints are linear. (e.g., Linear
Programming)
o Nonlinear: At least one is nonlinear.
 2. Unconstrained vs. Constrained
o Unconstrained: No restrictions on variables.
o Constrained: Variables must satisfy equations/inequalities.
3. Continuous vs. Discrete
o Continuous: Variables can take any real value.
o Discrete: Variables restricted to integers (e.g., scheduling, TSP).

3. Why Optimization? (Applications)

 Engineering: Structural design, resource allocation.
 Economics & Finance: Cost minimization, portfolio optimization.
 Machine Learning/AI: Training models by minimizing loss functions.
 Operations Research: Scheduling, transportation, supply chain.
 Robotics: Path planning, energy optimization.

4. Optimization Algorithms
Optimization algorithms provide systematic methods to solve these problems efficiently.

Categories:

1. Deterministic Algorithms (exact solutions)

o Linear Programming (Simplex Method, Interior Point Method)
o Gradient Descent (for continuous optimization)
o Dynamic Programming
2. Heuristic / Approximation Algorithms (near-optimal solutions)
o Greedy methods
o Local Search
o Genetic Algorithms
o Simulated Annealing

5. Key Concepts
 Objective Function → What we minimize/maximize.
 Constraints → Conditions that must be satisfied.
 Global Optimum → Best solution overall.
 Local Optimum → Best solution in a neighborhood but not overall.

6. Complexity
 Some optimization problems (like Linear Programming) can be solved in polynomial
time.
 Others (like Traveling Salesman Problem, Knapsack) are NP-hard.

. What is Gradient Descent?

  Gradient Descent is an iterative optimization algorithm used to minimize a
function.
 It works by moving step-by-step in the opposite direction of the gradient (steepest
descent).
 Commonly used in machine learning and statistics to minimize cost/loss functions.
 Formula:

θt+1=θt−η∇f(θt)

where

o θt = parameters at iteration t,
o η= learning rate,
o ∇f(θt) = gradient of the function.

2. How Does It Work?

1. Initialization → Start with an initial guess for parameters.
2. Compute Gradient → Calculate slope (gradient vector) at current position.
3. Update Step → Move parameters in the negative gradient direction.
o Step size depends on learning rate (η).
4. Iteration → Repeat until convergence (minimum found) or max iterations reached.

3. Applications in Machine Learning

 Linear Regression: Minimizes Mean Squared Error (MSE).
 Logistic Regression: Optimizes likelihood for classification.
 Neural Networks (Deep Learning): Backpropagation computes gradients, and
gradient descent updates the weights layer by layer.

4. Variants of Gradient Descent

1. Batch Gradient Descent
o Uses the entire dataset for gradient computation.
o Stable but computationally expensive.
2. Stochastic Gradient Descent (SGD)
o Updates using one random sample at a time.
o Faster, but noisy updates.
3. Mini-Batch Gradient Descent
o Uses small batches of data.
o Trade-off between efficiency and stability.
o Most common in deep learning.
 Gradient descent fig

Genetic Algorithms (GA) – Exam Notes

1. Introduction
 Genetic Algorithm (GA) is a search and optimization technique inspired by the
principles of natural selection and genetics.
 Belongs to the class of evolutionary algorithms.
 Works well for complex, non-linear, and non-differentiable problems where
traditional optimization fails.

2. Key Concepts
 Population: A set of candidate solutions.
 Chromosome: Representation of a solution (often as a binary string).
 Gene: A single value/part of a chromosome.
 Fitness Function: Evaluates how good a solution is.
 Generation: One iteration of the algorithm.

3. Basic Steps in Genetic Algorithm

1. Initialization: Generate an initial population randomly.
2. Fitness Evaluation: Calculate the fitness score of each individual.
3. Selection: Choose the best individuals (parents) based on fitness.
o Methods: Roulette Wheel, Tournament Selection, Rank Selection.
4. Crossover (Recombination): Combine two parents to produce new offspring.
o Example: Single-point crossover, two-point crossover.
5. Mutation: Randomly flip bits or modify genes to maintain diversity.
6. Replacement: Form the new generation using offspring and/or elite individuals.
7. Termination: Stop when convergence is reached (e.g., max generations, or no
improvement).

4. Advantages
 Can handle large and complex search spaces.
 Does not require gradient information (unlike Gradient Descent).
 Good for global optimization problems.

5. Limitations
  Computationally expensive (many evaluations needed).
 May converge slowly.
 Risk of premature convergence (getting stuck in suboptimal solutions).

6. Applications
 Machine Learning: Feature selection, hyperparameter tuning.
 Robotics: Path planning.
 Engineering Design: Structural optimization.
 Economics & Finance: Portfolio optimization.
 AI: Evolving strategies in games.

7. Example (Simple Flow)

1. Start with population → {10101, 11001, 11100}
2. Compute fitness → higher fitness = better solution.
3. Select parents → (10101, 11100).
4. Apply crossover → 10100, 11101.
5. Apply mutation → small bit flips.
6. New generation → better average fitness.
Difference between Gradient Descent and Genetic Algorithms
Feature Gradient Descent (GD) Genetic Algorithm (GA)

Deterministic, local search

Type Stochastic, global search optimization
optimization

Based on calculus (steepest descent Inspired by Darwin’s theory of natural

Inspiration
using gradient) selection and genetics

Single-point search (follows one Population-based search (works with

Search Method
solution path) multiple solutions at once)

Requires differentiable objective

Requirement Does not require gradient/differentiability
function

Exploration vs Exploits local slope → risk of local Explores large solution space → avoids
Exploitation minima local minima

Speed Usually faster (if convex function) Slower due to population evaluations

Converges to local minimum (global

Convergence Can approximate global optimum
only if convex)

Low per iteration (depends on Computationally expensive (fitness

Computation
gradient calculation) evaluation for many individuals)

Variants Batch, Stochastic, Mini-Batch GD Selection, Crossover, Mutation operators

Training ML models (linear

Optimization in robotics, engineering
Applications regression, neural networks, logistic
design, scheduling, feature selection
regression)

Particle swarm optimization-

Particle Swarm Optimization (PSO)

Optimization & Particle Swarm Optimization (PSO)

Optimization (Definition)

 Optimization = finding optimal parameter values of a system that:

o Fulfill design requirements.
o Achieve minimum cost (or maximum performance).
 Found in all fields of science, engineering, economics, and AI.
Limitations of Conventional (Deterministic) Algorithms

1. Work with single solution (no exploration of multiple solutions).

2. Often get stuck in local optima.
3. Struggle with unknown/complex search spaces.

Metaheuristic Optimization

 Developed to overcome these limitations.

 Use stochastic + population-based search.
 Examples:
o Particle Swarm Optimization (PSO)
o Genetic Algorithms (GA)
o Ant Colony Optimization (ACO)
o Grey Wolf Optimizer (GWO)
o Cuckoo Search Algorithm, etc.

Particle Swarm Optimization (PSO)

Inspiration

 Inspired by swarm intelligence in nature:

o Bird flocking.
o Fish schooling.
 Original intent (Kennedy & Eberhart, 1995):
o Simulate the graceful yet unpredictable motion of bird flocks.
 Key idea:
o Individual birds (particles) see only locally, but as a group they explore a
wider space efficiently.

Mathematical Model

Each particle has:

 Position: Xi​(candidate solution).

 Velocity: Vi(movement direction + speed).
 Fitness value: Quality of solution.

Each particle remembers:

 pBest: Its best position so far.

 gBest: Best position found by the entire swarm.

Algorithm Parameters

Problem parameters:

 Number of dimensions: d.
  Search space bounds: [minx,maxx

Algorithm hyperparameters:

 Number of particles: N
 Max iterations: max_iter
 Inertia weight: w.
 Cognitive coefficient: c1
 Social coefficient: c2.

PSO Algorithm Steps

1. Initialize swarm (random positions & velocities).

2. Evaluate fitness of each particle.
3. Update pBest: If current fitness better than previous best.
4. Update gBest: If any particle outperforms global best.
5. Update velocity: Vi​(t+1)=wVi​(t)+c1​r1​(pBesti​−Xi​(t))+c2​r2​(gBest−Xi​(t))
6. Update position:Xi(t+1)=Xi(t)+Vi(t+1)
7. Repeat until max iterations or convergence.

Advantages

 Easy to implement.
 Few parameters to tune.
 Works well for non-linear, multi-modal optimization.
 Gradient-free (does not require differentiable function).

Limitations

 May converge prematurely (local minima).

 Sensitive to parameter settings (w, c1, c2).
 Not ideal for discrete optimization.

Applications

 Neural network training.

 Function optimization (non-linear problems).
 Robotics (path planning).
 Engineering design optimization.
 Data clustering.