|
Convex Skull
In computational geometry, the potato peeling or convex skull problem is a problem of finding the convex polygon of the largest possible area that lies within a given non-convex simple polygon. It was posed independently by Goodman and Woo, and solved in polynomial time by Chang and Yap. The exponent of the polynomial time bound is high, but the same problem can also be accurately approximated in near-linear time. References {{reflist, refs= {{citation , last1 = Cabello , first1 = Sergio , last2 = Cibulka , first2 = Josef , last3 = Kynčl , first3 = Jan , last4 = Saumell , first4 = Maria , last5 = Valtr , first5 = Pavel , doi = 10.1137/16M1079695 , issue = 5 , journal = SIAM Journal on Computing , mr = 3708542 , pages = 1574–1602 , title = Peeling potatoes near-optimally in near-linear time , volume = 46 , year = 2017, arxiv = 1406.1368 {{citation , last1 = Chang , first1 = J. S. , last2 = Yap , first2 = C.-K. , doi = 10.1007/BF0218769 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Polygon
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 (not self-intersecting). Equivalently, a polygon is convex if every line that does not contain any edge intersects the polygon in at most two points. Strictly convex polygon A convex polygon is ''strictly'' convex if no line contains more than two vertices of the polygon. In a convex polygon, all interior angles are less than ''or equal'' to 180 degrees, while in a strictly convex polygon all interior angles are strictly less than 180 degrees. Properties The following properties of a simple polygon are all equivalent to convexity: *Every internal angle is less than or equal to 180 degrees. *Every point on every line segment between two points inside or on the boundary of the polygon remains inside or on the bou ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Simple Polygon
In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a Piecewise linear curve, 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. The sum of external angles of a simple polygon is 2\pi. Every simple polygon with n sides can be polygon triangulation, triangulated by n-3 of its diagonals, and by the art gallery theorem its interior is visible from some \lfloor n/3\rfloor of its vertices. Simple polygons are commonly seen as the input to computational geometry problems, including point in polygon testing, area computation, the convex hull of a simple polygon, triangulation, and Euclidean shortest paths. Other constructions in geometry related to simple polygons include Schwarz–Christoffel mapping, used to find conformal maps involving simple polygons, polygonalizat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is gener ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Approximation Algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Computing
The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation is ''SIAM J. Comput.'', its publisher and contributors frequently use the shorter abbreviation ''SICOMP''. SICOMP typically hosts the special issues of the IEEE Annual Symposium on Foundations of Computer Science (FOCS) and the Annual ACM Symposium on Theory of Computing (STOC), where about 15% of papers published in FOCS and STOC each year are invited to these special issues. For example, Volume 48 contains 11 out of 85 papers published in FOCS 2016. References External linksSIAM Journal on Computing on |
Discrete & Computational Geometry
'' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geometry. Abstracting and indexing The journal is indexed in: * ''Mathematical Reviews'' * '' Zentralblatt MATH'' * ''Science Citation Index'' * ''Current Contents ''Current Contents'' is a rapid alerting service database from Clarivate, formerly the Institute for Scientific Information and Thomson Reuters. It is published online and in several different printed subject sections. History ''Current Contents ...'' Notable articles Two articles published in ''Discrete & Computational Geometry'', one by Gil Kalai in 1992 with a proof of a subexponential upper bound on the diameter of a polytope and another by Samuel Ferguson in 2006 on the Kepler conjecture on optimal three-dimensional sphere packing, earned their authors the Fulk ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Geometriae Dedicata
''Geometriae Dedicata'' is a mathematical journal, founded in 1972, concentrating on geometry and its relationship to topology, group theory and the theory of dynamical systems. It was created on the initiative of Hans Freudenthal in Utrecht, the Netherlands.. It is published by Springer Netherlands. The Editor-in-Chief An editor-in-chief (EIC), also known as lead editor or chief editor, is a publication's editorial leader who has final responsibility for its operations and policies. The editor-in-chief heads all departments of the organization and is held accoun ... is Richard Alan Wentworth. References External links Springer site Geometry journals Springer Science+Business Media academic journals Algebra journals Dynamical systems journals Topology journals {{math-journal-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Hulls
Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytope, a polytope with a convex set of points ** Convex metric space, a generalization of the convexity notion in abstract metric spaces * Convex function, when the line segment between any two points on the graph of the function lies above or on the graph * Convex conjugate, of a function * Convexity (algebraic geometry), a restrictive technical condition for algebraic varieties originally introduced to analyze Kontsevich moduli spaces Economics and finance * Convexity (finance), second derivatives in financial modeling generally * Convexity in economics * Bond convexity, a measure of the sensitivity of the duration of a bond to changes in interest rates * Convex preferences, an individual's ordering of various outcomes Other uses * Convex Com ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
