Namespaces
Variants
Actions

Difference between revisions of "Geometric constructions"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
Line 2: Line 2:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A. Adler,  "Theorie der geometrischen Konstruktionen" , Göschen  (1906)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  D. Hilbert,  "Grundlagen der Geometrie" , Springer  (1913)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> , ''Enzyklopaedie der Elementarmathematik'' , Deutsch. Verlag Wissenschaft.  (1969)  (Translated from Russian)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  A. Adler,  "Theorie der geometrischen Konstruktionen" , Göschen  (1906)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  D. Hilbert,  "Grundlagen der Geometrie" , Springer  (1913)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top"> , ''Enzyklopaedie der Elementarmathematik'' , Deutsch. Verlag Wissenschaft.  (1969)  (Translated from Russian)</TD></TR>
 +
</table>
  
  
  
 
====Comments====
 
====Comments====
A construction problem is solvable by straight-edge (also called ruler) and compasses if and only if the [[Galois group|Galois group]] of the corresponding algebraic problem has the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g0442201.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g0442202.png" />. E.g., the regular <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g0442204.png" />-gon is constructible if and only if each odd prime power dividing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g0442205.png" /> is a Fermat prime <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g0442206.png" />, e.g., 3, 5, 17, 257, 65537, (?).
+
A construction problem is solvable by straight-edge (also called ruler) and compasses if and only if the [[Galois group]] of the corresponding algebraic problem has the order $2^k$, $k \in \mathbf{N}$. For example, the regular $n$-gon is constructible if and only if each odd prime power dividing $n$ is a [[Fermat prime]] $2^{2^m} + 1$, e.g., 3, 5, 17, 257, 65537, (?).
  
The classical constructions and construction problems described above are algorithms for constructing certain geometric objects (using primitive operations). The widespread use of geometric objects in computer graphics and computer aided design (CAD) has caused a modern version of algorithmic geometry to arise: computational geometry. In addition, computational problems arising in VLSI design have helped shape this field of research. The subject of computational geometry is precisely concerned with the algorithmic aspects of geometrical problems and related matters, such as the memory management aspects and computational complexity of such algorithms (cf. also [[Complexity theory|Complexity theory]] and [[Algorithm, computational complexity of an|Algorithm, computational complexity of an]]).
+
The classical constructions and construction problems described above are algorithms for constructing certain geometric objects (using primitive operations). The widespread use of geometric objects in computer graphics and computer aided design (CAD) has caused a modern version of algorithmic geometry to arise: computational geometry. In addition, computational problems arising in VLSI design have helped shape this field of research. The subject of computational geometry is precisely concerned with the algorithmic aspects of geometrical problems and related matters, such as the memory management aspects and computational complexity of such algorithms (cf. also [[Complexity theory]] and [[Algorithm, computational complexity of an]]).
  
 
Typical problems concern, e.g., finding the convex hull of a set of points, finding the intersection of two convex sets, constructing the Voronoi diagram of a set of points in the plane, point location search, describing the arrangement determined by a set of hyperplanes, and constructing triangulations.
 
Typical problems concern, e.g., finding the convex hull of a set of points, finding the intersection of two convex sets, constructing the Voronoi diagram of a set of points in the plane, point location search, describing the arrangement determined by a set of hyperplanes, and constructing triangulations.
  
Given a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g0442207.png" /> of points in the plane, the corresponding Voronoi diagram partitions the plane into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g0442208.png" /> polygonal regions, one for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g0442209.png" />. The open Voronoi region of a point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422010.png" /> consists of all points of the plane closer to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422011.png" /> than to any other point of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422012.png" />. A Voronoi diagram can be constructed in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422013.png" /> time (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422014.png" />) and can be searched in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422015.png" /> time.
+
Given a set $S$ of points in the plane, the corresponding Voronoi diagram partitions the plane into $\sharp S$ polygonal regions, one for each $s \in S$. The open Voronoi region of a point $s$ consists of all points of the plane closer to $s$ than to any other point of $S$.. A Voronoi diagram can be constructed in $O(n \log n)$ time (where $n = \sharp S$) and can be searched in $O(\log n)$ time.
  
 
Point location search refers to determining in what region of a given subdivision (of the plane, or space<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422016.png" />) a given point lies.
 
Point location search refers to determining in what region of a given subdivision (of the plane, or space<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422016.png" />) a given point lies.
  
Given a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422017.png" /> of hyperplanes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422018.png" />, they divide the space in a number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422019.png" />-dimensional regions, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422020.png" />, and the arrangement determined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422021.png" /> is that corresponding subdivision. For example, three lines in general position in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044220/g04422022.png" /> divide the plane into 7 two-dimensional regions, 9 one-dimensional segments and 3 zero-dimensional points. Determining the hyperplane arrangement means describing this subdivision (and storing it (efficiently) in memory).
+
Given a set $H$ of hyperplanes in $\mathbf{R}^n$, they divide the space in a number of $d$-dimensional regions, $d = 0,\ldots,n$, and the arrangement determined by $H$ is that corresponding subdivision. For example, three lines in general position in $\mathbf{R}^2$ divide the plane into 7 two-dimensional regions, 9 one-dimensional segments and 3 zero-dimensional points. Determining the hyperplane arrangement means describing this subdivision (and storing it (efficiently) in memory).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Bieberbach,  "Theorie der geometrischen Konstruktionen" , Birkhäuser  (1952)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  K. Mehlhorn,  "Multidimensional searching and computational geometry" , Springer  (1984)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Edelsbrunner,  "Algorithms in combinatorial geometry" , Springer  (1987)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Bieberbach,  "Theorie der geometrischen Konstruktionen" , Birkhäuser  (1952)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  K. Mehlhorn,  "Multidimensional searching and computational geometry" , Springer  (1984)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Edelsbrunner,  "Algorithms in combinatorial geometry" , Springer  (1987)</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Revision as of 19:05, 17 December 2015

The solution of certain geometric problems with the aid of various instruments (straight-edge, compasses, etc.), which are assumed to be perfectly accurate. The selection of the instruments determines the class of problems solvable by these means. The straight-edge and compasses are the two basic instruments for geometric constructions. A construction problem will be solvable with the aid of a straight-edge and compasses if the coordinates of the point sought can be written as expressions involving a finite number of the operations of addition, multiplication, division, and extraction of a square root, applied to the coordinates of given points (see, for example, Cyclotomic polynomials). If such expressions do not exist, the problem cannot be solved with the aid of a straight-edge and compasses. Such problems include, for example, duplication of the cube; trisection of an angle; and quadrature of the circle. Any construction problem that is solvable with the aid of compasses and a straight-edge can also be solved with the aid of a different set of instruments: the compasses alone (the Mohr–Mascheroni construction, G. Mohr, 1672; L. Mascheroni, 1797); a straight-edge with two parallel edges, which may be replaced by a triangle (A. Adler, 1890); a straightedge and a circle with a marked centre given in the plane of the figure (Poncelet–Steiner constructions, J.V. Poncelet, 1822; J. Steiner, 1833).

References

[1] A. Adler, "Theorie der geometrischen Konstruktionen" , Göschen (1906)
[2] D. Hilbert, "Grundlagen der Geometrie" , Springer (1913)
[3] , Enzyklopaedie der Elementarmathematik , Deutsch. Verlag Wissenschaft. (1969) (Translated from Russian)


Comments

A construction problem is solvable by straight-edge (also called ruler) and compasses if and only if the Galois group of the corresponding algebraic problem has the order $2^k$, $k \in \mathbf{N}$. For example, the regular $n$-gon is constructible if and only if each odd prime power dividing $n$ is a Fermat prime $2^{2^m} + 1$, e.g., 3, 5, 17, 257, 65537, (?).

The classical constructions and construction problems described above are algorithms for constructing certain geometric objects (using primitive operations). The widespread use of geometric objects in computer graphics and computer aided design (CAD) has caused a modern version of algorithmic geometry to arise: computational geometry. In addition, computational problems arising in VLSI design have helped shape this field of research. The subject of computational geometry is precisely concerned with the algorithmic aspects of geometrical problems and related matters, such as the memory management aspects and computational complexity of such algorithms (cf. also Complexity theory and Algorithm, computational complexity of an).

Typical problems concern, e.g., finding the convex hull of a set of points, finding the intersection of two convex sets, constructing the Voronoi diagram of a set of points in the plane, point location search, describing the arrangement determined by a set of hyperplanes, and constructing triangulations.

Given a set $S$ of points in the plane, the corresponding Voronoi diagram partitions the plane into $\sharp S$ polygonal regions, one for each $s \in S$. The open Voronoi region of a point $s$ consists of all points of the plane closer to $s$ than to any other point of $S$.. A Voronoi diagram can be constructed in $O(n \log n)$ time (where $n = \sharp S$) and can be searched in $O(\log n)$ time.

Point location search refers to determining in what region of a given subdivision (of the plane, or space) a given point lies.

Given a set $H$ of hyperplanes in $\mathbf{R}^n$, they divide the space in a number of $d$-dimensional regions, $d = 0,\ldots,n$, and the arrangement determined by $H$ is that corresponding subdivision. For example, three lines in general position in $\mathbf{R}^2$ divide the plane into 7 two-dimensional regions, 9 one-dimensional segments and 3 zero-dimensional points. Determining the hyperplane arrangement means describing this subdivision (and storing it (efficiently) in memory).

References

[a1] L. Bieberbach, "Theorie der geometrischen Konstruktionen" , Birkhäuser (1952)
[a2] K. Mehlhorn, "Multidimensional searching and computational geometry" , Springer (1984)
[a3] H. Edelsbrunner, "Algorithms in combinatorial geometry" , Springer (1987)
How to Cite This Entry:
Geometric constructions. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Geometric_constructions&oldid=36958
This article was adapted from an original article by P.S. ModenovA.S. Parkhomenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article