The Central Idea
Spatial optimization asks us to choose an arrangement that performs better according to a geometric objective.
A general structure is
\[ \boxed{ \text{spatial choices} + \text{constraints} + \text{objective} \longrightarrow \text{best feasible arrangement} }. \]The objective may involve minimizing distance, maximizing coverage, increasing packing density, reducing overlap, or balancing several competing goals.
Packing Problems
A packing problem asks how objects can be placed within a region without unacceptable overlap.
Examples include:
- boxes in a warehouse;
- circles in a container;
- components on a board;
- products on pallets;
- data storage or communication regions under geometric constraints.
Packing Density
A simple packing-efficiency measure is
\[ \boxed{ \text{packing density} = \frac{\text{area or volume occupied by packed objects}} {\text{total available area or volume}} }. \]The result is often expressed as a decimal or percentage.
Example: Rectangular Packing Density
A container has area
\[ 120\text{ m}^2. \]Packed objects occupy
\[ 90\text{ m}^2. \]The density is
\[ \frac{90}{120}=0.75. \]Therefore,
\[ \boxed{75\%}. \]Feasibility Comes Before Optimization
Before asking whether a packing is efficient, we must ask whether it is possible.
If objects overlap when overlap is forbidden, the arrangement is not feasible.
Likewise, an object that extends beyond the container violates the boundary constraint.
Circle Nonoverlap Constraint
Two circles with centers
\[ C_1,\qquad C_2 \]and radii
\[ r_1,\qquad r_2 \]do not overlap when
\[ \boxed{ \|C_2-C_1\| \ge r_1+r_2 }. \]Example: Circle Separation
Two circles have radii
\[ 2 \]and
\[ 3. \]Their centers must be at least
\[ 2+3=5 \]units apart to avoid overlap.
Therefore,
\[ \boxed{d\ge5}. \]Boundary Clearance
A packed object may also require clearance from a container boundary.
For a circle of radius \(r\) inside a rectangular container, the center must remain at least distance \(r\) from every wall if touching the boundary is forbidden.
Clearance requirements can increase this minimum center-to-wall distance.
Grid Packing
A simple packing method places equal objects on a rectangular grid.
If circular objects have diameter \(d\), adjacent grid centers may be separated by \(d\) in horizontal and vertical directions.
This arrangement is easy to calculate but is not always the densest possible arrangement.
Staggered Packing
Equal circles can often be packed more efficiently by staggering rows.
Neighboring centers then form equilateral-triangle patterns rather than square-grid patterns.
This reduces unused gaps between circles.
Local Geometry of Staggered Circle Packing
If equal circles have radius \(r\), adjacent touching centers are separated by
\[ 2r. \]In the triangular center pattern, the vertical separation between adjacent staggered rows is
\[ \boxed{\sqrt{3}\,r}. \]Three-Dimensional Packing
Packing problems also occur in three dimensions.
Examples include:
- spheres in containers;
- cartons in trucks;
- inventory in storage racks;
- components inside machines.
Orientation can become an important decision variable because rotating an object may change whether it fits.
Axis-Aligned Box Packing
If identical boxes of dimensions
\[ a\times b\times c \]are placed without rotation inside a container
\[ L\times W\times H, \]a simple axis-aligned count is
\[ \boxed{ \left\lfloor\frac{L}{a}\right\rfloor \left\lfloor\frac{W}{b}\right\rfloor \left\lfloor\frac{H}{c}\right\rfloor }. \]Example: Box Count
A container measures
\[ 10\times8\times6 \]units, and each box measures
\[ 2\times2\times3. \]Without rotation,
\[ \left\lfloor\frac{10}{2}\right\rfloor=5, \] \[ \left\lfloor\frac{8}{2}\right\rfloor=4, \] \[ \left\lfloor\frac{6}{3}\right\rfloor=2. \]Therefore,
\[ \boxed{5\cdot4\cdot2=40\text{ boxes}}. \]Covering Problems
A covering problem asks how to place regions so every required point is contained in at least one service region.
Examples include:
- wireless access points;
- emergency-service stations;
- sensor coverage;
- sprinkler coverage;
- lighting;
- inspection regions.
Coverage Region
If a facility serves every point within distance \(R\), its idealized coverage region in a plane is a disk:
\[ \boxed{ (x-a)^2+(y-b)^2\le R^2 }. \]The center
\[ (a,b) \]is the facility location.
Coverage Area
A circular service region of radius \(R\) has area
\[ \boxed{ A=\pi R^2 }. \]Increasing radius therefore increases ideal coverage area quadratically.
Overlap in Covering
Overlap can be useful because it provides redundancy.
Too much overlap, however, may waste resources if the goal is to cover a region efficiently.
Covering problems therefore often balance:
\[ \boxed{ \text{complete coverage} \quad\text{against}\quad \text{excess overlap} }. \]Gaps
A coverage gap is a required point not contained in any service region.
If facilities have centers \(C_i\) and common service radius \(R\), a point \(P\) is uncovered when
\[ \boxed{ \|P-C_i\|>R \quad\text{for every facility }i }. \]Nearest-Facility Problems
Given several facilities, a point may be assigned to whichever facility is nearest.
For facilities at
\[ F_1,F_2,\ldots,F_n, \]point \(P\) is assigned to facility \(F_k\) when
\[ \boxed{ \|P-F_k\| \le \|P-F_i\| \quad \text{for all }i }. \]Perpendicular Bisectors as Service Boundaries
For two facilities \(A\) and \(B\), points equally distant from them satisfy
\[ \boxed{ d(P,A)=d(P,B) }. \]In the Euclidean plane, this locus is the perpendicular bisector of segment \(AB\).
Voronoi Regions
A Voronoi region consists of points closer to one site than to any competing site.
A collection of sites divides the plane into nearest-site territories.
This is useful for:
- service territories;
- facility assignment;
- spatial competition;
- nearest-neighbor organization.
Why Voronoi Geometry Is Useful
If travel cost is approximated by Euclidean distance, Voronoi boundaries identify where two facilities are equally competitive.
Crossing a boundary changes which facility is nearest.
Facility Location
A facility-location problem asks where one or more facilities should be placed.
Objectives may include minimizing:
- average travel distance;
- maximum travel distance;
- total weighted distance;
- response time;
- construction or operating cost.
Weighted Distance
Suppose demand point \(P_i\) has importance or demand weight \(w_i\).
A simple total-distance objective for facility location \(X\) is
\[ \boxed{ J(X) = \sum_i w_i\,d(X,P_i) }. \]The optimization problem is to choose \(X\) that makes \(J(X)\) as small as possible.
Centroid as a Spatial Average
For points with coordinates
\[ (x_i,y_i), \]the unweighted coordinate average is
\[ \boxed{ \bar{x} = \frac1n\sum_i x_i, \qquad \bar{y} = \frac1n\sum_i y_i }. \]The point
\[ (\bar{x},\bar{y}) \]is the centroid of the point set under equal weighting.
Weighted Centroid
If points have weights \(w_i\), then a weighted centroid is
\[ \boxed{ \bar{x} = \frac{\sum_iw_ix_i}{\sum_iw_i}, \qquad \bar{y} = \frac{\sum_iw_iy_i}{\sum_iw_i} }. \]This is a useful center-of-demand measure, although it does not solve every facility-location objective.
Example: Weighted Center
Two demand points are
\[ P_1=(0,0), \qquad P_2=(10,0), \]with weights
\[ w_1=1, \qquad w_2=3. \]Then
\[ \bar{x} = \frac{1(0)+3(10)}{1+3} = 7.5, \] \[ \bar{y}=0. \]Therefore,
\[ \boxed{(7.5,0)}. \]Minimax Location
Some applications care about the worst-served point rather than average distance.
A minimax objective has the form
\[ \boxed{ \min_X \max_i d(X,P_i) }. \]This seeks a location that makes the maximum distance to all required points as small as possible.
Routing Problems
A routing problem asks how to travel through a spatial system efficiently.
Examples include:
- delivery routes;
- road navigation;
- robot paths;
- network cables;
- inspection routes;
- airline or shipping networks.
Shortest Path in Open Euclidean Space
With no obstacles and unrestricted straight-line travel, the shortest path between two points is the line segment joining them.
Its length is
\[ \boxed{ d= \sqrt{ (x_2-x_1)^2 +(y_2-y_1)^2 } }. \]Obstacles Change the Shortest Path
If a direct segment crosses a forbidden region, the shortest feasible route must bend around the obstacle.
The optimization therefore becomes:
\[ \boxed{ \text{minimize path length} \quad \text{subject to obstacle avoidance} }. \]Waypoint Routing
A route can be approximated by connecting waypoints
\[ P_0,P_1,\ldots,P_n. \]The total route length is
\[ \boxed{ L = \sum_{i=0}^{n-1} d(P_i,P_{i+1}) }. \]Example: Two-Segment Route
A route travels from
\[ A=(0,0) \]to
\[ B=(3,4) \]and then to
\[ C=(9,4). \]First segment:
\[ AB=5. \]Second segment:
\[ BC=6. \]Therefore,
\[ \boxed{L=11}. \]Networks and Graphs
A transportation or communication system can be represented as a graph.
The graph contains:
- vertices, representing locations;
- edges, representing allowed connections.
Each edge may have a weight such as distance, time, cost, or risk.
Weighted Shortest Path
If route edges have costs
\[ c_1,c_2,\ldots,c_k, \]the route cost is
\[ \boxed{ C_{\text{route}} = \sum_{i=1}^k c_i }. \]A shortest-path algorithm seeks the allowed route with minimum total cost.
Distance Is Not Always the Objective
The shortest route in distance may not be the fastest or least expensive.
An edge weight could represent:
- travel time;
- fuel use;
- tolls;
- energy;
- risk;
- congestion;
- combined cost.
Traveling-Salesperson Structure
Some routing problems require visiting many locations and returning to the start.
The objective may be to find an ordering
\[ P_1,P_2,\ldots,P_n \]that minimizes total tour length.
This is much harder than simply finding one shortest path between two fixed points.
Routing with Capacity
Real delivery systems may include limits such as vehicle capacity.
If route demand is
\[ \sum_i q_i \]and vehicle capacity is \(Q\), a feasible route must satisfy
\[ \boxed{ \sum_i q_i\le Q }. \]Geometry and resource constraints must then be optimized together.
Routing with Time Windows
Some destinations can only be served during specific time intervals.
A route may be spatially short but infeasible if arrival times violate these windows.
Optimization therefore often includes both spatial and temporal constraints.
Network Design
Sometimes the problem is not merely to travel on an existing network but to decide which connections should exist.
Examples include:
- road networks;
- pipeline systems;
- electrical grids;
- fiber networks;
- drainage systems.
Connecting All Sites
Suppose several sites must all be connected.
One possible objective is to minimize total connection length while preserving connectivity.
In graph terms, this leads to minimum-spanning-tree structure.
Minimum Spanning Tree
A spanning tree connects all vertices without cycles.
A minimum spanning tree has the smallest total edge weight among all spanning trees.
Its total cost is
\[ \boxed{ C_{\text{tree}} = \sum_{e\in T}w_e }. \]Direct Connections Versus Hub Systems
A system can connect every pair directly or route traffic through hubs.
Direct connectivity may reduce travel distance but require many links.
Hub systems reduce infrastructure count but may increase travel distance.
Spatial optimization often balances these competing effects.
Coverage Versus Routing
A facility can be well placed for coverage but poorly placed for network routing.
For example, a geometric center may minimize average Euclidean distance but lie far from usable roads.
The relevant distance metric must match the real movement system.
Euclidean Distance
Euclidean distance in the plane is
\[ \boxed{ d_E = \sqrt{(\Delta x)^2+(\Delta y)^2} }. \]This measures direct straight-line separation.
Manhattan Distance
In a grid-like movement system where horizontal and vertical travel are allowed but diagonal travel is not, a useful metric is
\[ \boxed{ d_M = |\Delta x| + |\Delta y| }. \]This is often called Manhattan or taxicab distance.
Example: Comparing Metrics
For displacement
\[ \Delta x=3, \qquad \Delta y=4, \]Euclidean distance is
\[ d_E=5. \]Manhattan distance is
\[ d_M=3+4=7. \]Therefore,
\[ \boxed{d_E=5,\qquad d_M=7}. \]Chebyshev Distance
If a grid system allows horizontal, vertical, and diagonal movement with equal cost per step, a useful metric is
\[ \boxed{ d_C = \max(|\Delta x|,|\Delta y|) }. \]Different movement rules produce different geometries.
Optimization Depends on the Metric
A point that is optimal under Euclidean distance may not be optimal under road-network, Manhattan, or travel-time distance.
The distance definition is part of the model, not merely a calculation detail.
Spatial Constraints
A feasible location may need to satisfy several geometric conditions.
For example:
\[ x_{\min}\le x\le x_{\max}, \] \[ y_{\min}\le y\le y_{\max}, \] \[ d(X,O_j)\ge r_j, \] \[ d(X,D_i)\le R_i. \]These constraints define a feasible region.
Feasible Regions
A feasible region is the set of all choices satisfying every required constraint.
Optimization occurs only within this region.
If the feasible region is empty, no solution satisfies all constraints simultaneously.
Objective Functions
An objective function measures how good a feasible solution is.
Examples include
\[ \boxed{ \text{minimize }L } \]for route length,
\[ \boxed{ \text{maximize }A_{\text{covered}} } \]for coverage, or
\[ \boxed{ \text{maximize }\rho } \]for packing density.
Single-Objective Optimization
A single-objective problem has one primary quantity to optimize.
For example,
\[ \boxed{ \min_X \sum_i d(X,P_i) }. \]The feasible location \(X\) with the smallest total distance is preferred.
Multiple Objectives
Real spatial decisions may involve conflicting goals.
A facility might need to:
- minimize travel distance;
- avoid expensive land;
- maximize coverage;
- remain near infrastructure;
- stay far from hazards.
No single location may be best for every objective at once.
Weighted Objectives
Multiple objectives can sometimes be combined:
\[ \boxed{ J = w_1J_1+w_2J_2+\cdots+w_nJ_n }. \]The weights represent the relative importance assigned to the different goals.
Choosing those weights is a modeling decision.
Discrete Versus Continuous Spatial Decisions
A facility location can be continuous if it may be placed anywhere in a region.
It is discrete if it must be chosen from a fixed list of candidate sites.
Discrete and continuous versions of the same spatial problem can require very different solution methods.
Grid Search
One simple numerical method evaluates an objective at many candidate grid points.
The best sampled point is selected:
\[ \boxed{ X^* = \arg\min_{X\in G}J(X) }. \]Finer grids can improve resolution but require more evaluations.
Local Versus Global Optima
A local optimum is better than nearby feasible choices.
A global optimum is best among all feasible choices.
Complex spatial objectives can contain several local optima.
Heuristics
Some spatial optimization problems become computationally difficult as the number of objects or locations grows.
A heuristic seeks a good solution without necessarily proving that it is globally optimal.
Heuristics are common in routing, packing, scheduling, and facility placement.
Greedy Strategies
A greedy method repeatedly chooses the locally best available next step.
For example, a nearest-neighbor routing heuristic may travel next to the closest unvisited destination.
This can be fast, but the final route need not be globally shortest.
Nearest-Neighbor Example
Suppose a route begins at \(A\), and the unvisited sites are at distances
\[ 3,\quad5,\quad8. \]A nearest-neighbor step chooses the site at distance
\[ \boxed{3}. \]The process then repeats from the new site.
Clustering
Spatial points can be grouped into clusters before routing or facility assignment.
A cluster contains points considered close according to a chosen metric.
Clustering can reduce a large problem into smaller regional subproblems.
Service Territories
Facilities can be assigned territories using nearest-site rules, capacity limits, administrative boundaries, or travel-time regions.
The resulting territories need not be identical to ordinary Euclidean Voronoi regions when the movement metric is not Euclidean.
Location-Allocation Problems
A location-allocation problem combines two decisions:
- where facilities should be placed;
- which demand points should be assigned to each facility.
Changing facility positions changes assignments, and changing assignments can change the preferred facility positions.
Capacity-Constrained Assignment
If facility \(j\) has capacity \(C_j\), assigned demand must satisfy
\[ \boxed{ \sum_{i\in A_j}q_i \le C_j }. \]The nearest facility may therefore be unavailable if its capacity is already exhausted.
Spatial Optimization with Uncertainty
Demand, travel time, obstacle conditions, and service radius may be uncertain.
A robust spatial plan seeks acceptable performance across a range of plausible conditions rather than relying on one exact scenario.
Sensitivity
A solution is sensitive when small changes in assumptions produce large changes in the preferred arrangement.
If several candidate solutions have nearly equal objective values, a small change in weights or distances may change which one appears optimal.
Common Error: Maximizing Density Before Checking Feasibility
An arrangement with high apparent density is invalid if objects overlap or cross container boundaries when those actions are forbidden.
Feasibility constraints must be satisfied before comparing objective values.
Common Error: Assuming the Geometric Center Is Always Best
A geometric center may be useful, but it is not automatically optimal.
Demand weights, road networks, obstacles, capacities, and objective choice can move the best location elsewhere.
Common Error: Using Euclidean Distance for a Network Problem
Straight-line distance may underestimate actual travel if movement must follow roads, corridors, or graph edges.
Use a distance metric consistent with the actual movement system.
Common Error: Confusing Packing with Covering
Packing tries to place objects without unwanted overlap.
Covering tries to ensure every required point lies inside at least one service region.
Overlap is usually undesirable in packing but can be useful or necessary in covering.
Common Error: Assuming Nearest Means Best
The nearest facility may lack capacity, have longer actual travel time, or be unavailable.
Distance is only one possible assignment criterion.
Common Error: Ignoring Return Travel
A route that must return to its starting point is a tour, not merely a path from the start to the final destination.
The return segment must be included in total route cost.
Common Error: Treating a Heuristic as a Proof of Optimality
A heuristic can produce a good route or arrangement without proving that no better solution exists.
Approximate solution quality and proven optimality are different claims.
A Reliable Procedure for Packing Problems
- Identify object shapes and dimensions.
- Identify container geometry.
- Write nonoverlap and boundary constraints.
- Determine whether rotation is allowed.
- Construct a feasible arrangement.
- Calculate occupied area or volume.
- Compute packing density or another objective.
- Compare alternative feasible arrangements.
A Reliable Procedure for Covering Problems
- Identify the region or demand points requiring coverage.
- Identify the shape and radius of each service region.
- Determine whether overlap is allowed or desired.
- Locate uncovered gaps.
- Evaluate total covered area or covered demand.
- Adjust facility locations to improve coverage or reduce redundancy.
A Reliable Procedure for Routing Problems
- Identify the required start, destinations, and end condition.
- Identify allowable connections.
- Choose the relevant metric or edge cost.
- Include obstacles, capacities, or time restrictions.
- Construct one or more feasible routes.
- Calculate total route cost.
- Compare alternatives using the stated objective.
- Distinguish a good heuristic solution from a proven optimum.
A Reliable Procedure for Facility-Location Problems
- Identify demand points and weights.
- Identify candidate or feasible facility locations.
- Choose the correct distance or travel metric.
- Write the objective function.
- Include capacity and exclusion constraints.
- Evaluate candidate locations or solve the continuous optimization model.
- Check worst-case and average performance as appropriate.
- Test sensitivity to changed assumptions.
Example: Full Spatial Optimization Workflow
Three equally weighted demand points are located at
\[ A=(0,0), \qquad B=(6,0), \qquad C=(3,6). \]A simple center-of-demand estimate uses the centroid:
\[ \bar{x} = \frac{0+6+3}{3} = 3, \] \[ \bar{y} = \frac{0+0+6}{3} = 2. \]Therefore,
\[ \boxed{X=(3,2)}. \]This point is a useful spatial average, but whether it is truly optimal depends on the objective. A minimax objective, road-network objective, capacity constraint, or forbidden region could produce a different best location.
Practice 1: Packing Density
Packed objects occupy
\[ 72\text{ m}^2 \]inside a container of area
\[ 96\text{ m}^2. \]Find the packing density.
Practice 2: Circle Separation
Two nonoverlapping circles have radii
\[ 4 \]and
\[ 7. \]What is the minimum distance between their centers?
Practice 3: Coverage Area
An ideal circular service region has radius
\[ 5\text{ km}. \]Find its area.
Practice 4: Weighted Centroid
Demand points are
\[ P_1=(0,0) \]with weight \(2\), and
\[ P_2=(8,0) \]with weight \(6\).
Find the weighted centroid.
Practice 5: Route Length
A route travels through points
\[ A=(0,0), \quad B=(3,4), \quad C=(3,10). \]Find the total route length.
Practice 6: Euclidean and Manhattan Distance
Find both distances between
\[ (1,2) \]and
\[ (7,10). \]Practice 7: Box Packing
A container measures
\[ 12\times9\times6, \]and identical boxes measure
\[ 3\times3\times2. \]How many fit under the simple axis-aligned no-rotation model?
Practice 8: Capacity Constraint
A vehicle has capacity
\[ 100 \]units. A proposed route serves demands
\[ 20,\quad35,\quad50. \]Is the route feasible under the capacity constraint?
Practice 9: Nearest Facility
Point
\[ P=(4,0) \]is served by the nearer of facilities
\[ A=(0,0) \]and
\[ B=(10,0). \]Which facility is nearer?
Practice 10: Identify the Error
A student uses the nearest-neighbor routing heuristic and claims the route must be globally shortest.
Explain the error.
Practice Answers
Practice 1
\[ \rho = \frac{72}{96} = 0.75. \]Therefore,
\[ \boxed{75\%}. \]Practice 2
\[ d_{\min}=4+7=11. \]Therefore,
\[ \boxed{11}. \]Practice 3
\[ A=\pi(5)^2=25\pi. \]Therefore,
\[ \boxed{25\pi\text{ km}^2}. \]Practice 4
\[ \bar{x} = \frac{2(0)+6(8)}{2+6} = \frac{48}{8} = 6. \] \[ \bar{y}=0. \]Therefore,
\[ \boxed{(6,0)}. \]Practice 5
First segment:
\[ AB=5. \]Second segment:
\[ BC=6. \]Therefore,
\[ \boxed{L=11}. \]Practice 6
Coordinate differences are
\[ \Delta x=6, \qquad \Delta y=8. \]Euclidean distance:
\[ d_E=\sqrt{6^2+8^2}=10. \]Manhattan distance:
\[ d_M=6+8=14. \]Therefore,
\[ \boxed{d_E=10,\qquad d_M=14}. \]Practice 7
\[ \left\lfloor\frac{12}{3}\right\rfloor=4, \] \[ \left\lfloor\frac{9}{3}\right\rfloor=3, \] \[ \left\lfloor\frac{6}{2}\right\rfloor=3. \]Therefore,
\[ \boxed{4\cdot3\cdot3=36\text{ boxes}}. \]Practice 8
\[ 20+35+50=105. \]Since
\[ 105>100, \]the route is
\[ \boxed{\text{not feasible under the stated capacity}}. \]Practice 9
\[ d(P,A)=4, \] \[ d(P,B)=6. \]Therefore,
\[ \boxed{A\text{ is nearer}}. \]Practice 10
Nearest-neighbor routing is a heuristic. It chooses the locally nearest unvisited destination at each step, but those local choices can produce a longer overall tour than another ordering.
Therefore, the method may provide a good route without proving global optimality.
What to Remember
- Packing places objects efficiently while respecting nonoverlap and boundary constraints.
- Packing density compares occupied area or volume with total available area or volume.
- Covering seeks to ensure that required points lie inside one or more service regions.
- Overlap can be undesirable in packing but useful in covering.
- Nearest-facility boundaries arise from equal-distance loci such as perpendicular bisectors.
- Voronoi regions divide space according to nearest-site relationships.
- Facility-location objectives can minimize average, weighted, or worst-case distance.
- Centroids are useful spatial averages but are not universal optimal facility locations.
- Routing depends on the allowed network and the chosen edge cost.
- Euclidean, Manhattan, Chebyshev, and network distances represent different movement rules.
- Shortest paths, tours, and network-design problems are distinct optimization structures.
- Capacity, time windows, obstacles, and service requirements turn geometry into constrained optimization.
- Feasible regions contain all choices satisfying the constraints.
- Objective functions rank feasible solutions.
- Heuristics can produce useful solutions without guaranteeing global optimality.
The central relationship is:
\[ \boxed{ \text{geometry} + \text{constraints} + \text{objective} \longrightarrow \text{optimized spatial arrangement} }. \]Where We Go Next
Packing, covering, routing, and facility placement turn spatial structure into decisions. Many modern applications begin with spatial information that must first be collected, represented, measured, and interpreted from images or other data sources.
The next lesson, Spatial Data and Imaging, develops applied spatial reasoning for pixels, coordinates, resolution, sampling, image measurements, spatial data structures, transformations, and extracting geometric information from digital representations.