View source for Arrangement (space partition)

{{short description|Decomposition into connected open cells of lower dimensions, by a finite set of objects}}
[[File:Complete-quads.svg|thumb|300px|Line arrangements]]
In [[discrete geometry]], an '''arrangement''' is the decomposition of the d-dimensional [[linear space|linear]], [[affine geometry|affine]], or [[projective geometry|projective]] space into connected [[abstract cell complex|cell]]s of different dimensions, induced by a finite collection of geometric objects, which are usually of dimension one less than the dimension of the space, and often of the same type as each other, such as [[hyperplane]]s or [[sphere]]s.

==Definition==
For a set <math>A</math> of objects in <math>\mathbb{R}^d</math>, the cells in the arrangement
are the [[Connected component (topology)|connected component]]s of sets of the form
<math>(\cap X)\setminus\cup(A\setminus X)</math>
for subsets <math>X</math> of <math>A</math>. That is, for each <math>X</math> the cells are the connected components of the points that belong to every object in <math>X</math> and do not belong to any other object. For instance the cells of an arrangement of lines in the Euclidean plane are of three types:
*Isolated points, for which <math>X</math> is the subset of all lines that pass through the point.
*Line segments or rays, for which <math>X</math> is a [[singleton set]] of one line. The segment or ray is a connected component of the points that belong only to that line and not to any other line of <math>A</math>
*[[Convex polygon]]s (possibly unbounded), for which <math>X</math> is the empty set, and its intersection (the [[empty intersection]]) is the whole space. These polygons are the connected components of the subset of the plane formed by removing all the lines in <math>A</math>.

==Types of arrangement==
Of particular interest are the [[arrangements of lines]] and [[arrangements of hyperplanes]].

More generally, geometers have studied arrangements of other types of curves in the plane, and of other more complicated types of surface.<ref name="as00">{{citation
 |last1=Agarwal 
 |first1=P. K. 
 |author1-link=Pankaj K. Agarwal 
 |last2=Sharir 
 |first2=M. 
 |author2-link=Micha Sharir 
 |contribution=Arrangements and their applications 
 |editor1-last=Sack 
 |editor1-first=J.-R. 
 |editor1-link=Jörg-Rüdiger Sack 
 |editor2-last=Urrutia 
 |editor2-first=J. 
 |editor2-link=Jorge Urrutia Galicia 
 |pages=49–119 
 |publisher=Elsevier 
 |title=Handbook of Computational Geometry 
 |url=http://biogeometry.duke.edu/pubs-pankaj/surveys/arrangement-survey.ps.gz
 |archive-url=https://web.archive.org/web/20070610070151/http://biogeometry.duke.edu/pubs-pankaj/surveys/arrangement-survey.ps.gz
 |url-status=dead
 |archive-date=2007-06-10
 |year=2000 
}}.</ref> Arrangements in [[complex number|complex]] [[vector space]]s have also been studied; since complex lines do not partition the complex plane into multiple connected components, the combinatorics of vertices, edges, and cells does not apply to these types of space, but it is still of interest to study their symmetries and topological properties.<ref>{{citation
 | last1 = Orlik | first1 = P.
 | last2 = Terao | first2 = H.
 | publisher = Springer-Verlag
 | series = Grundlehren der mathematischen Wissenschaften
 | title = Arrangements of Hyperplanes
 | volume = 300
 | year = 1992}}.</ref>

==Applications==
An interest in the study of arrangements was driven by advances in [[computational geometry]], where the arrangements were unifying structures for many problems. Advances in study of more complicated objects, such as [[algebraic surface]]s, contributed to "real-world" applications, such as [[motion planning]] and [[computer vision]].<ref>{{citation|first=Dan|last=Halperin|contribution=Arrangements|title=Handbook of Discrete and Computational Geometry|edition=2nd|year=2004|isbn=978-1-58488-301-2}}.</ref>

==References==
{{reflist}}

[[Category:Computational geometry]]
[[Category:Discrete geometry]]