Hubbry Logo
Half-space (geometry)Half-space (geometry)Main
Open search
Half-space (geometry)
Community hub
Half-space (geometry)
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Half-space (geometry)
Half-space (geometry)
Half-space (geometry)
View on Wikipedia
from Wikipedia

In geometry, a half-space is either of the two parts into which a plane divides the three-dimensional Euclidean space.[1] If the space is two-dimensional, then a half-space is called a half-plane (open or closed).[2][3] A half-space in a one-dimensional space is called a half-line[4] or ray.

More generally, a half-space is either of the two parts into which a hyperplane divides an n-dimensional space. That is, the points that are not incident to the hyperplane are partitioned into two convex sets (i.e., half-spaces), such that any subspace connecting a point in one set to a point in the other must intersect the hyperplane.[5]

A half-space can be either open or closed. An open half-space is either of the two open sets produced by the subtraction of a hyperplane from the affine space. A closed half-space is the union of an open half-space and the hyperplane that defines it.

The open (closed) upper half-space is the half-space of all such that . The open (closed) lower half-space is defined similarly, by requiring that be negative (non-positive).

A half-space may be specified by a linear inequality, derived from the linear equation that specifies the defining hyperplane. A strict linear inequality specifies an open half-space: A non-strict one specifies a closed half-space: Here, one assumes that not all of the real numbers a1, a2, ..., an are zero.

A half-space is a convex set.

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Half-space (geometry)

View on Grokipedia
from Grokipedia
In geometry, a half-space is the portion of an on one side of a , consisting of all points that satisfy a defined by the . Formally, in Rn\mathbb{R}^n, a closed half-space is the set {x∈Rn∣aTx≤b}\{ \mathbf{x} \in \mathbb{R}^n \mid \mathbf{a}^T \mathbf{x} \leq b \}, where a≠0\mathbf{a} \neq \mathbf{0} is a normal vector to the and bb is a scalar, while the open half-space excludes the boundary by using strict inequality <<. These sets are unbounded convex regions that generalize the concept of a half-plane in two dimensions to higher-dimensional spaces. Half-spaces are fundamental building blocks in convex geometry, as any convex set can be represented as an intersection of half-spaces, and polyhedral convex sets specifically arise from finite intersections of closed half-spaces. This representation, known as the half-space description or H-description, contrasts with the vertex-based V-description and is essential for algorithms in linear programming and optimization, where feasible regions are often defined by such inequalities. In computational geometry, half-space intersections enable the construction of convex hulls and support applications in areas like computer-aided design, robotics, and machine learning for modeling decision boundaries in support vector machines.

Definition

Formal Definition

In Euclidean space Rn\mathbb{R}^n, a half-space is defined as one of the two connected components of the complement of a hyperplane. This hyperplane divides the space into two unbounded regions, each constituting a half-space. A hyperplane in Rn\mathbb{R}^n is an affine subspace of dimension n−1n-1, given by the set {x∈Rn∣a⋅x=b}\{ x \in \mathbb{R}^n \mid a \cdot x = b \}, where a∈Rna \in \mathbb{R}^n is a non-zero vector serving as the normal to the hyperplane, and b∈Rb \in \mathbb{R} is a scalar determining its position. The vector aa is perpendicular to the hyperplane and orients it, while the term bb generalizes the definition beyond linear hyperplanes through the origin to affine ones. The corresponding half-spaces are then the sets {x∈Rn∣a⋅x<b}\{ x \in \mathbb{R}^n \mid a \cdot x < b \} (open half-space) and {x∈Rn∣a⋅x≤b}\{ x \in \mathbb{R}^n \mid a \cdot x \leq b \} (closed half-space). The strict inequality in the open half-space excludes the hyperplane itself as the boundary, whereas the non-strict inequality includes it, making the closed half-space the closure of the open one. The normal vector aa orients the half-space such that the open half-space {a⋅x<b}\{ a \cdot x < b \} lies on the side opposite to the direction of aa relative to the hyperplane. In two dimensions, this specializes to a half-plane.

Open and Closed Half-Spaces

A half-space in Euclidean space can be defined as either open or closed, depending on whether it includes its bounding hyperplane. The open half-space excludes the hyperplane and consists solely of points strictly satisfying the defining linear inequality, such as {x∈Rn∣⟨a,x⟩<b}\{ x \in \mathbb{R}^n \mid \langle a, x \rangle < b \} for a normal vector a≠0a \neq 0 and scalar bb. In contrast, the closed half-space incorporates the hyperplane, including all points that satisfy the non-strict inequality {x∈Rn∣⟨a,x⟩≤b}\{ x \in \mathbb{R}^n \mid \langle a, x \rangle \leq b \}. The bounding hyperplane itself serves as the boundary for both types of half-spaces. For the open half-space, this boundary has empty intersection with the set, meaning no points on the hyperplane belong to it. Consequently, the open half-space is disjoint from its boundary, and every point in it is an interior point of the set. The closed half-space, however, fully contains its boundary, making the hyperplane part of the set. This distinction affects topological properties, such as the open half-space being an open set in the Euclidean topology, while the closed version is closed. In terms of set-theoretic operations, the intersection of any collection of open half-spaces remains open, preserving the exclusion of boundaries from all involved hyperplanes. Similarly, the union of open half-spaces is open, though it may result in a set that is no longer a single half-space if the half-spaces do not align appropriately. For closed half-spaces, intersections are closed, but unions are not necessarily closed, as boundary points from one may not be covered by the other. These properties highlight how openness influences the behavior under basic set operations in convex geometry. Notation for half-spaces often distinguishes the two sides of a hyperplane using superscripts based on the orientation of the normal vector aa, which points toward the "positive" side. Thus, H+H^+ typically denotes the half-space where ⟨a,x⟩>b\langle a, x \rangle > b (open) or ≥b\geq b (closed), while H−H^- denotes the opposite side with ⟨a,x⟩<b\langle a, x \rangle < b or ≤b\leq b. This convention aids in specifying directionality in applications like separation theorems.

Properties

Geometric Properties

A half-space in Euclidean space Rn\mathbb{R}^n (n≥1n \geq 1) is unbounded in every direction orthogonal to its bounding and in all directions away from the hyperplane, allowing points within it to extend infinitely far without crossing the boundary. This unbounded nature arises from the linear inequality defining the half-space, such as {x∈Rn:⟨a,x⟩≤b}\{ x \in \mathbb{R}^n : \langle a, x \rangle \leq b \}, where vectors a≠0a \neq 0 permit translation along rays parallel to the hyperplane or pointing outward indefinitely. Every half-space is a convex set, meaning that for any two points x,yx, y in the half-space, the entire line segment [x,y][x, y] remains contained within it. This property follows directly from the linearity of the defining inequality: if ⟨a,x⟩≤b\langle a, x \rangle \leq b and ⟨a,y⟩≤b\langle a, y \rangle \leq b, then for λ∈[0,1]\lambda \in [0,1], ⟨a,λx+(1−λ)y⟩=λ⟨a,x⟩+(1−λ)⟨a,y⟩≤b\langle a, \lambda x + (1-\lambda) y \rangle = \lambda \langle a, x \rangle + (1-\lambda) \langle a, y \rangle \leq b. Both open and closed variants of half-spaces share this convexity. Parallel half-spaces, defined by hyperplanes with the same normal vector aa but different thresholds (e.g., ⟨a,x⟩≤b1\langle a, x \rangle \leq b_1 and ⟨a,x⟩≥b2\langle a, x \rangle \geq b_2 with b2<b1b_2 < b_1), exhibit separation properties that divide Rn\mathbb{R}^n into distinct regions: the intersection forms a slab bounded in the direction of aa, while their complements allow strict separation of convex sets lying on opposite sides. Such configurations enable the isolation of subsets, as guaranteed by the for disjoint convex sets. The Lebesgue measure of a half-space in Rn\mathbb{R}^n (n≥1n \geq 1) is infinite, as its unbounded extent in n−1n-1 dimensions along the hyperplane combined with infinite extension in the normal direction yields an integral over an unbounded domain that diverges. For instance, integrating the standard over such a set encompasses regions of arbitrarily large finite volume, precluding a finite total.

Topological Properties

In Rn\mathbb{R}^n, both the open half-space {x∈Rn∣a⋅x>b}\{ x \in \mathbb{R}^n \mid a \cdot x > b \} and the closed half-space {x∈Rn∣a⋅x≥b}\{ x \in \mathbb{R}^n \mid a \cdot x \geq b \} (for some a∈Rn∖{0}a \in \mathbb{R}^n \setminus \{0\} and b∈Rb \in \mathbb{R}) are path-connected topological spaces. Path-connectedness follows from their convexity: for any two points p,qp, q in the half-space, the straight-line segment [p,q][p, q] lies entirely within it, providing a continuous path from pp to qq. This property holds because half-spaces are convex subsets of Rn\mathbb{R}^n, and convex sets in Euclidean space are path-connected. The open half-space is homeomorphic to Rn\mathbb{R}^n. This equivalence arises because it is an open, connected subset of Rn\mathbb{R}^n, and such subsets share the topological structure of ; an explicit can be constructed via an mapping the half-space to the upper half-plane followed by a radial or logarithmic mapping to cover the full plane in lower dimensions, generalizing to higher dimensions. In contrast, the closed half-space is not homeomorphic to Rn\mathbb{R}^n due to its boundary. Neither the open nor the closed half-space is compact in the standard . Compactness in Rn\mathbb{R}^n requires a set to be closed and bounded by the Heine-Borel theorem, but half-spaces are unbounded, extending infinitely in certain directions. The closed half-space is closed but unbounded, while the open half-space fails to be closed. The open half-space forms an nn-dimensional without boundary, as every point admits an open neighborhood homeomorphic to Rn\mathbb{R}^n. The closed half-space, however, is an nn-dimensional manifold with boundary, where interior points (away from the defining ) have neighborhoods homeomorphic to Rn\mathbb{R}^n, and boundary points have neighborhoods homeomorphic to the closed half-space itself; the boundary is the hyperplane, which is an (n−1)(n-1)-dimensional manifold without boundary.

Examples in Low Dimensions

In Two Dimensions (Half-Planes)

In two dimensions, a half-space corresponds to a half-plane, which is the region of the R2\mathbb{R}^2 consisting of all points lying strictly on one side of a given straight line. This line serves as the boundary, dividing the entire plane into two complementary half-planes that together cover all points except those on the boundary itself. Consider a straight line defined by the equation ax+by=cax + by = c, where aa, bb, and cc are real constants with aa and bb not both zero. This line partitions R2\mathbb{R}^2 into two half-planes: the open set {(x,y)∣ax+by<c}\{(x, y) \mid ax + by < c\} on one side and {(x,y)∣ax+by>c}\{(x, y) \mid ax + by > c\} on the other. Visually, each half-plane forms an unbounded region bounded solely by the line, extending infinitely in every direction away from it, much like an infinite "sheet" folded along the line. For simpler coordinate-based intuition, horizontal half-planes arise when the bounding line is parallel to the x-axis, such as y=ky = k for some constant kk, yielding the half-plane {(x,y)∣y>k}\{(x, y) \mid y > k\} above the line or {(x,y)∣y<k}\{(x, y) \mid y < k\} below it. Similarly, vertical half-planes are defined by lines parallel to the y-axis, like x=mx = m, resulting in regions such as {(x,y)∣x>m}\{(x, y) \mid x > m\} to the right or {(x,y)∣x<m}\{(x, y) \mid x < m\} to the left, facilitating straightforward analysis in Cartesian coordinates.

In Three Dimensions

In three dimensions, a half-space in R3\mathbb{R}^3 is the region consisting of all points on one side of (including or excluding) an infinite plane, formally defined by the inequality ax+by+cz+d≥0ax + by + cz + d \geq 0, where (a,b,c)≠(0,0,0)(a, b, c) \neq (0, 0, 0) and d∈Rd \in \mathbb{R}, with the plane itself given by ax+by+cz+d=0ax + by + cz + d = 0. The normal vector (a,b,c)(a, b, c) to the plane determines the orientation, pointing toward the side where the inequality holds strictly. A representative example is the upper half-space, defined as the set of points (x,y,z)∈R3(x, y, z) \in \mathbb{R}^3 satisfying z≥0z \geq 0, bounded by the xyxy-plane where z=0z = 0. This region intuitively corresponds to the above the ground level in a physical , extending infinitely in the positive zz-direction while unbounded in xx and yy. Visually, a three-dimensional half-space has infinite and occupies one half of the entire R3\mathbb{R}^3, divided by the bounding plane that separates it from the complementary half-space. Unlike bounded solids, it lacks finite extent in the direction normal to the plane but fills all on its designated side. Half-spaces in R3\mathbb{R}^3 relate to rays and coordinate directions by specifying orientations such as "above" or "below" relative to vector; for instance, in the upper half-space example, the positive zz-axis ray defines the direction into the interior from the boundary plane. This directional property facilitates spatial partitioning, akin to extending two-dimensional half-planes into volumetric regions.

Applications

In Convex Geometry

In convex geometry, half-spaces serve as the fundamental building blocks for constructing , as every in can be expressed as the of all half-spaces that contain it. This representation underscores the separating property inherent to convexity, where for any point outside the set, a supporting half-space exists that includes the entire while excluding the exterior point. Formally, a nonempty closed convex set C⊆RnC \subseteq \mathbb{R}^n equals the of all closed half-spaces HH such that C⊆HC \subseteq H. This provides a precise characterization that links the intrinsic geometry of closed convex sets to their half-space descriptions. For general convex sets, the may involve open half-spaces as well. For bounded convex sets, particularly in finite dimensions, the representation simplifies to finite intersections of half-spaces, known as the H-representation. This is especially relevant for polyhedra and polytopes, where a polyhedron is defined as the intersection of finitely many half-spaces, each specified by a linear inequality ai⋅x≤bi\mathbf{a}_i \cdot \mathbf{x} \leq b_i. Bounded polyhedra, or polytopes, thus admit a compact H-representation consisting of a finite system of such inequalities that define their facets. This finite description contrasts with the potentially infinite intersections needed for general closed convex sets, highlighting the polyhedral structure's algebraic tractability. The H-representation is dual to the V-representation of , where a polytope is equivalently the of a of vertices (extreme points). According to the fundamental theorem of polytope representations, every polytope in Rn\mathbb{R}^n possesses both an H-representation as the of finitely many half-spaces and a V-representation as the of finitely many points, with conversions between them possible though computationally intensive. This duality, first systematically explored in classical works on convex , enables efficient geometric computations and underscores the equivalence of inequality-based and vertex-based descriptions for bounded convex polyhedra.

In Optimization and Linear Programming

In linear programming, the feasible region of a problem is defined as the intersection of a finite number of half-spaces, each corresponding to a linear inequality constraint, resulting in a that encodes the set of admissible solutions. This geometric representation allows for the visualization and analysis of optimization problems, where the objective is to maximize or minimize a over this bounded or unbounded . The polyhedral structure ensures convexity, facilitating the application of algorithms that exploit this property to find optimal solutions efficiently. A canonical example is the standard form of a linear program: maximize c⋅x\mathbf{c} \cdot \mathbf{x} subject to Ax≤bA\mathbf{x} \leq \mathbf{b}, where AA is an m×nm \times n matrix, b∈Rm\mathbf{b} \in \mathbb{R}^m, and c∈Rn\mathbf{c} \in \mathbb{R}^n. Each inequality ai⋅x≤bi\mathbf{a}_i \cdot \mathbf{x} \leq b_i (for the ii-th row of AA and bb) delineates a half-space, and the is their , forming a polyhedron in Rn\mathbb{R}^n. Non-negativity constraints x≥0\mathbf{x} \geq \mathbf{0} can be incorporated as additional half-spaces. This formulation underscores how half-spaces directly shape the geometry of solvable optimization instances. The , introduced by in , solves such linear programs by navigating the vertices of this feasible region, which arise at the intersections of the bounding hyperplanes from the half-spaces. Starting from an initial (a vertex), the algorithm iteratively pivots to an adjacent vertex by adjusting variables along an edge, improving the objective value until optimality is reached, thereby traversing the combinatorial structure induced by the half-space constraints. This vertex-enumeration approach leverages the fact that an optimal solution lies at a vertex of the . Linear programming duality further highlights the role of half-spaces, as the primal problem's —defined by half-space intersections from Ax≤bA\mathbf{x} \leq \mathbf{b}—corresponds to the dual problem's variables, while the dual's constraints form half-spaces for the primal variables. For the primal maximization max⁡c⋅x\max \mathbf{c} \cdot \mathbf{x} subject to Ax≤bA\mathbf{x} \leq \mathbf{b}, x≥0\mathbf{x} \geq \mathbf{0}, the dual is min⁡b⋅y\min \mathbf{b} \cdot \mathbf{y} subject to ATy≥cA^T \mathbf{y} \geq \mathbf{c}, y≥0\mathbf{y} \geq \mathbf{0}, with its also a . The strong duality theorem guarantees that if both problems are feasible and bounded, their optimal values coincide, linking the half-space geometries of primal and dual.

References

  1. https://www.cs.umd.edu/class/spring2020/cmsc754/Lects/lect06-duality.pdf
  2. https://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-249.pdf
  3. https://www.cs.utexas.edu/~ecprice/courses/randomized/fa23/scribe/lec21.pdf
  4. https://math.dartmouth.edu/~doyle/docs/finite/fm2/scan/6.pdf
  5. https://www.cis.upenn.edu/~cis6100/convex1-09.pdf
  6. https://www.cs.rpi.edu/~cutler/classes/computationalgeometry/S22/lectures/06_half_space_intersections.pdf
  7. https://www.cis.upenn.edu/~cis6100/sp06stanley.pdf
  8. http://www.seas.ucla.edu/~vandenbe/cvxbook/bv_cvxbook.pdf
  9. https://mathworld.wolfram.com/Half-Space.html
  10. https://www.math.cmu.edu/~ttkocz/teaching/1920/conv-discr-geom-notes.pdf
  11. https://wiki.math.ntnu.no/linearmethods/basicspaces/openandclosed
  12. https://ti.inf.ethz.ch/ew/lehre/ApproxGeom07/notes/Ch1Introduction.pdf
  13. https://www.karlin.mff.cuni.cz/~rataj/konv_telesa/Weil-Conv_Geom.pdf
  14. https://www.akshayagrawal.com/files/separation-theorems.pdf
  15. https://www.math.cmu.edu/~ttkocz/teaching/1819/asympt-conv-geom-notes.pdf
  16. https://www.math.stonybrook.edu/~olga/mat364-fall14/connected.pdf
  17. https://moussong.web.elte.hu/bsm/firststeps_25.pdf
  18. https://mathresearch.utsa.edu/wiki/index.php?title=Heine-Borel_Theorem
  19. https://people.eecs.berkeley.edu/~jrs/meshpapers/edels/L-07.pdf
  20. https://openlab.citytech.cuny.edu/2022-spring-medu-3000-reitz/files/2022/03/Wu-Axioms-and-Theorems-of-Geometry.pdf
  21. https://www.math.brown.edu/tbanchof/STG/ma8/papers/kadams/geometry_extended.html
  22. https://people.tamu.edu/~j-epstein//141/notes/Ch3.pdf
  23. https://www.math.ucla.edu/~baker/149.1.02w/handouts/kk_linear_geom.pdf
  24. https://pressbooks.pub/linearalgebraandapplications/chapter/hyperplanes-and-half-spaces/
  25. https://mathworld.wolfram.com/Half-Plane.html
  26. https://www.cs.cmu.edu/~ggordon/10725-F12/scribes/10725_Lecture3.pdf
  27. https://theory.stanford.edu/~trevisan/cs261/lecture05.pdf
  28. https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s22/www/notes/lec15.pdf
  29. https://www.whitman.edu/documents/Academics/Mathematics/lewis.pdf
  30. https://hua-zhou.github.io/teaching/st758-2014fall/top10/simplex.pdf
  31. https://algoparc.ics.hawaii.edu/~nodari/teaching/s15/Notes/Topic-21.html
  32. https://web.stanford.edu/~ashishg/msande111/notes/chapter4.pdf
  33. https://courses.cs.duke.edu/spring17/compsci330/Notes/LPDU.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.