In geometry, a bitangent to a curve C is a line L that touches C in two distinct points P and Q and that has the same direction as C at these points. That is, L is a tangent line at P and at Q.
In geometry, a bitangent to a curve C is a line L that touches C in two distinct points P and Q and that has the same direction as C at these points. That is, L is a tangent line at P and at Q.
In general, an algebraic curve will have infinitely many secant lines, but only finitely many bitangents.
Bézout's theorem implies that an algebraic plane curve with a bitangent must have degree at least 4. The case of the 28 bitangents of a quartic was a celebrated piece of geometry of the nineteenth century, a relationship being shown to the 27 lines on the cubic surface.
The four bitangents of two disjoint convex polygons may be found efficiently by an algorithm based on binary search in which one maintains a binary search pointer into the lists of edges of each polygon and moves one of the pointers left or right at each steps depending on where the tangent lines to the edges at the two pointers cross each other. This bitangent calculation is a key subroutine in data structures for maintaining convex hulls dynamically ( Overmars & van Leeuwen 1981 ). PocchiolaandVegter ( 1996a , 1996b ) describe an algorithm for efficiently listing all bitangent line segments that do not cross any of the other curves in a system of multiple disjoint convex curves, using a technique based on pseudotriangulation.
Bitangents may be used to speed up the visibility graph approach to solving the Euclidean shortest path problem: the shortest path among a collection of polygonal obstacles may only enter or leave the boundary of an obstacle along one of its bitangents, so the shortest path can be found by applying Dijkstra's algorithm to a subgraph of the visibility graph formed by the visibility edges that lie on bitangent lines ( Rohnert 1986 ).
A bitangent differs from a secant line in that a secant line may cross the curve at the two points it intersects it. One can also consider bitangents that are not lines; for instance, the symmetry set of a curve is the locus of centers of circles that are tangent to the curve in two points.
Bitangents to pairs of circles figure prominently in Jakob Steiner's 1826 construction of the Malfatti circles, in the belt problem of calculating the length of a belt connecting two pulleys, in Casey's theorem characterizing sets of four circles with a common tangent circle, and in Monge's theorem on the collinearity of intersection points of certain bitangents.
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.
In geometry, a secant is a line that intersects a curve at a minimum of two distinct points. The word secant comes from the Latin word secare, meaning to cut. In the case of a circle, a secant intersects the circle at exactly two points. A chord is the line segment determined by the two points, that is, the interval on the secant whose ends are the two points.
In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a simple polygon. Equivalently, a polygon is convex if every line that does not contain any edge intersects the polygon in at most two points.
In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.
In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.
In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge represents a visible connection between them. That is, if the line segment connecting two locations does not pass through any obstacle, an edge is drawn between them in the graph. When the set of locations lies in a line, this can be understood as an ordered series. Visibility graphs have therefore been extended to the realm of time series analysis.
Geometry is a branch of mathematics concerned with questions of shape, size, relative position of figures, and the properties of space. Geometry is one of the oldest mathematical sciences.
In geometry, visibility is a mathematical abstraction of the real-life notion of visibility.
In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.
The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.
In Euclidean plane geometry, a tangent line to a circle is a line that touches the circle at exactly one point, never entering the circle's interior. Tangent lines to circles form the subject of several theorems, and play an important role in many geometrical constructions and proofs. Since the tangent line to a circle at a point P is perpendicular to the radius to that point, theorems involving tangent lines often involve radial lines and orthogonal circles.
In geometry, a supporting lineL of a curve C in the plane is a line that contains a point of C, but does not separate any two points of C. In other words, C lies completely in one of the two closed half-planes defined by L and has at least one point on L.
In geometry, a convex curve is a plane curve that has a supporting line through each of its points. There are many other equivalent definitions of these curves, going back to Archimedes. Examples of convex curves include the convex polygons, the boundaries of convex sets, and the graphs of convex functions. Important subclasses of convex curves include the closed convex curves, the smooth curves that are convex, and the strictly convex curves, which have the additional property that each supporting line passes through a unique point of the curve.
John E. Hershberger is an American computer scientist and software professional, a principal engineer at Mentor Graphics Corporation since 1993. He is known for his research in computational geometry and algorithm engineering.
In discrete geometry, an opaque set is a system of curves or other set in the plane that blocks all lines of sight across a polygon, circle, or other shape. Opaque sets have also been called barriers, beam detectors, opaque covers, or opaque forests. Opaque sets were introduced by Stefan Mazurkiewicz in 1916, and the problem of minimizing their total length was posed by Frederick Bagemihl in 1959.
In discrete geometry and computational geometry, the relative convex hull or geodesic convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.
The Pestov–Ionin theorem in the differential geometry of plane curves states that every simple closed curve of curvature at most one encloses a unit disk.