|
Constrained Delaunay Triangulation
In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges, unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation. Definition The input to the constrained Delaunay triangulation problem is a planar straight-line graph, a set of points and non-crossing line segments in the plane. The constrained Delaunay triangulation of this input is a triangulation of its convex hull, including all of the input segments as edges, and using only the vertices of the input. For every additional edge e added to this input to make it into a triangulation, there should exist a circle through the endpoints of e, such that any vertex interior to the circle is blocked f ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Geometry
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. Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(''n''2) and O(''n'' log ''n'') may be the difference between days and seconds of computation. The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (CAD/ CAM), but many problems in computational geometry ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Delaunay Triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934. For a set of points on the same line there is no Delaunay triangulation (the notion of triangulation is degenerate for this case). For four or more points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: each of the two possible triangulations that split the quadrangle into two triangles satisfies the "Delaunay condition", i.e., the requirement that the circumcircles of all triangles have empty interiors. By considering circumscribed spheres, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algorithmica
''Algorithmica'' is a monthly peer-reviewed scientific journal focusing on research and the application of computer science algorithms. The journal was established in 1986 and is published by Springer Science+Business Media. The editor in chief is Mohammad Hajiaghayi. Subject coverage includes sorting, searching, data structures, computational geometry, and linear programming, VLSI, distributed computing, parallel processing, computer aided design, robotics, graphics, data base design, and software tool A programming tool or software development tool is a computer program that software developers use to create, debug, maintain, or otherwise support other programs and applications. The term usually refers to relatively simple programs, that can ...s. Springer Science+Business Media. 2013 Abstractin ...
|
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''/Engineering, Computing and Technology Notable articles The articles by Gil Kalai with a proof of a subexponential upper bound on the diameter of a polyhedron and by Samuel Ferguson on the Kepler conjecture, both published in Discrete & Computational geometry, earned their author the Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e .... References External links ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Planar Straight-line Graph
In computational geometry and geometric graph theory, a planar straight-line graph, in short ''PSLG'', (or ''straight-line plane graph'', or ''plane straight-line graph'') is a term used for an embedding of a planar graph in the plane such that its edges are mapped into straight-line segments. Fáry's theorem (1948) states that every planar graph has this kind of embedding. In computational geometry, PSLGs have often been called planar subdivisions, with an assumption or assertion that subdivisions are polygonal rather than having curved boundaries. PSLGs may serve as representations of various maps, e.g., geographical maps in geographical information systems. Special cases of PSLGs are triangulations ( polygon triangulation, point-set triangulation). Point-set triangulations are maximal PSLGs in the sense that it is impossible to add straight edges to them while keeping the graph planar. Triangulations have numerous applications in various areas. PSLGs may be seen as a speci ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset. Convex hulls of open sets are open, and convex hulls of compact sets are compact. Every compact convex set is the convex hull of its extreme points. The convex hull operator is an example of a closure operator, and every antimatroid can be represented by applying this closure operator to finite sets of points. The algorithmic problems of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces, and its dual problem of intersecting half-spaces, are fundamental problems of co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Jonathan Shewchuk
Jonathan Richard Shewchuk is a Professor in Computer Science at the University of California, Berkeley. He obtained his B.S. in Physics and Computing Science from Simon Fraser University in 1990, and his M.S. and Ph.D. in Computer Science from Carnegie Mellon University, the latter in 1997. He conducts research in scientific computing, computational geometry (especially mesh generation, numerical robustness, and surface reconstruction), numerical methods, and physically based animation. He is also the author of Three Sins of Authors In Computer Science And Math'. In 2003 he was awarded J. H. Wilkinson Prize for Numerical Software for writing thTrianglesoftware package which computes high-quality unstructured triangular meshes. He appears in online course videos of CS 61B: Data Structures class in University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Simple Polygon
In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If the sides intersect then the polygon is not simple. The qualifier "simple" is frequently omitted, with the above definition then being understood to define a polygon in general. The definition given above ensures the following properties: * A polygon encloses a region (called its interior) which always has a measurable area. * The line segments that make up a polygon (called sides or edges) meet only at their endpoints, called vertices (singular: vertex) or less formally "corners". * Exactly two edges meet at each vertex. * The number of edges always equals the number of vertices. Two edges meeting at a corner are usually required to form an angle that is not straight (180°); otherwise, the collinear line segments will be considered part ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Time
In 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 generally express ... [...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 DBLP [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Topographic
Topography is the study of the forms and features of land surfaces. The topography of an area may refer to the land forms and features themselves, or a description or depiction in maps. Topography is a field of geoscience and planetary science and is concerned with local detail in general, including not only relief, but also natural, artificial, and cultural features such as roads, land boundaries, and buildings. In the United States, topography often means specifically ''relief'', even though the USGS topographic maps record not just elevation contours, but also roads, populated places, structures, land boundaries, and so on. Topography in a narrow sense involves the recording of relief or terrain, the three-dimensional quality of the surface, and the identification of specific landforms; this is also known as geomorphometry. In modern usage, this involves generation of elevation data in digital form (DEM). It is often considered to include the graphic representation of the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Surveying
Surveying or land surveying is the technique, profession, art, and science of determining the terrestrial two-dimensional or three-dimensional positions of points and the distances and angles between them. A land surveying professional is called a land surveyor. These points are usually on the surface of the Earth, and they are often used to establish maps and boundaries for ownership, locations, such as the designed positions of structural components for construction or the surface location of subsurface features, or other purposes required by government or civil law, such as property sales. Surveyors work with elements of geodesy, geometry, trigonometry, regression analysis, physics, engineering, metrology, programming languages, and the law. They use equipment, such as total stations, robotic total stations, theodolites, GNSS receivers, retroreflectors, 3D scanners, LiDAR sensors, radios, inclinometer, handheld tablets, optical and digital levels, subsurface locat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
_crop.jpg "Click for more on -> Surveying")