WikiMili The Free Encyclopedia

In computational geometry, the **relative neighborhood graph (RNG**) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points *p* and *q* by an edge whenever there does not exist a third point *r* that is closer to both *p* and *q* than they are to each other. This graph was proposed by Godfried Toussaint in 1980 as a way of defining a structure from a set of points that would match human perceptions of the shape of the set.^{ [1] }^{ [2] }

**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 history stretching back to antiquity.

**Godfried Theodore Patrick Toussaint** is a Canadian Computer Scientist, a Professor of Computer Science, and the Head of the Computer Science Program at New York University Abu Dhabi (NYUAD) in Abu Dhabi, United Arab Emirates. He is considered to be the father of computational geometry in Canada. He does research on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition, motion planning, visualization, knot theory, linkage (mechanical) reconfiguration, the art gallery problem, polygon triangulation, the largest empty circle problem, unimodality, and others. Other interests include meander (art), compass and straightedge constructions, instance-based learning, music information retrieval, and computational music theory.

Supowit (1983) showed how to construct the relative neighborhood graph efficiently in O(*n* log *n*) time.^{ [3] } It can be computed in O (*n*) expected time, for random set of points distributed uniformly in the unit square.^{ [4] } The relative neighborhood graph can be computed in linear time from the Delaunay triangulation of the point set.^{ [5] }^{ [6] }

In probability theory and statistics, the **continuous uniform distribution** or **rectangular distribution** is a family of symmetric probability distributions such that for each member of the family, all intervals of the same length on the distribution's support are equally probable. The support is defined by the two parameters, *a* and *b*, which are its minimum and maximum values. The distribution is often abbreviated *U*(*a*,*b*). It is the maximum entropy probability distribution for a random variable *X* under no constraint other than that it is contained in the distribution's support.

In mathematics, a **unit square** is a square whose sides have length 1. Often, "the" unit square refers specifically to the square in the Cartesian plane with corners at the four points (0, 0), (1, 0), (0, 1), and (1, 1).

In mathematics and computational geometry, a **Delaunay triangulation** for a given set **P** of discrete points in a plane 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 angle 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.

Because it is defined only in terms of the distances between points, the relative neighborhood graph can be defined for point sets in any dimension,^{ [1] }^{ [7] }^{ [8] } and for non-Euclidean metrics.^{ [1] }^{ [5] }^{ [9] }^{ [10] }

The relative neighborhood graph is an example of a lens-based beta skeleton. It is a subgraph of the Delaunay triangulation. In turn, the Euclidean minimum spanning tree is a subgraph of it, from which it follows that it is a connected graph.

In 2-dimensional geometry, a **lens** is a convex set bounded by two circular arcs joined to each other at their endpoints. In order for this shape to be convex, both arcs must bow outwards (convex-convex). This shape can be formed as the intersection of two circular disks. It can also be formed as the union of two circular segments, joined along a common chord.

In computational geometry and geometric graph theory, a ** β-skeleton** or

The **Euclidean minimum spanning tree** or **EMST** is a minimum spanning tree of a set of *n* points in the plane, where the weight of the edge between each pair of points is the Euclidean distance between those two points. In simpler terms, an EMST connects a set of dots using lines such that the total length of all the lines is minimized and any dot can be reached from any other by following the lines.

The Urquhart graph, the graph formed by removing the longest edge from every triangle in the Delaunay triangulation, was originally proposed as a fast method to compute the relative neighborhood graph.^{ [11] } Although the Urquhart graph sometimes differs from the relative neighborhood graph^{ [12] } it can be used as an approximation to the relative neighborhood graph.^{ [13] }

In computational geometry, the **Urquhart graph** of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation.

In mathematics, a **Voronoi diagram** is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. That set of points is specified beforehand, and for each seed there is a corresponding region consisting of all points closer to that seed than to any other. These regions are called Voronoi cells. The Voronoi diagram of a set of points is dual to its Delaunay triangulation.

In computational geometry, **polygon triangulation** is the decomposition of a polygonal area **P** into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is **P**.

A **triangulation of a set of points** in the Euclidean space is a simplicial complex that covers the convex hull of , and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.

The **art gallery problem** or **museum problem** is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards who together can observe the whole gallery. In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon.

**Nearest neighbor search** (**NNS**), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values. Formally, the nearest-neighbor (NN) search problem is defined as follows: given a set *S* of points in a space *M* and a query point *q* ∈ *M*, find the closest point in *S* to *q*. Donald Knuth in vol. 3 of *The Art of Computer Programming* (1973) called it the **post-office problem**, referring to an application of assigning to a residence the nearest post office. A direct generalization of this problem is a *k*-NN search, where we need to find the *k* closest points.

In mathematics and computational geometry, the **Gabriel graph** of a set of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph with vertex set in which any points and are adjacent precisely if they are distinct, i.e. , and the closed disc of which line segment is a diameter contains no other elements of . Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed balls. Gabriel graphs are named after K. Ruben Gabriel, who introduced them in a paper with Robert R. Sokal in 1969.

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.

A **geometric spanner** or a ** t-spanner graph** or a

In computational geometry, a **planar straight-line graph**, in short *PSLG*, 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.

The **nearest neighbor graph** (**NNG**) for a set of *n* objects *P* in a metric space is a directed graph with *P* being its vertex set and with a directed edge from *p* to *q* whenever *q* is a nearest neighbor of *p*.

**Jump-and-Walk** is an algorithm for point location in triangulations. Surprisingly, the algorithm does not need any preprocessing or complex data structures except some simple representation of the triangulation itself. The predecessor of Jump-and-Walk was due to Lawson (1977) and Green and Sibson (1978), which picks a random starting point S and then walks from S toward the query point Q one triangle at a time. But no theoretical analysis was known for these predecessors until after mid-1990s.

In statistics and computational geometry, the notion of **centerpoint** is a generalization of the median to data in higher-dimensional Euclidean space. Given a set of points in *d*-dimensional space, a centerpoint of the set is a point such that any hyperplane that goes through that point divides the set of points in two roughly equal subsets: the smaller part should have at least a 1/(*d* + 1) fraction of the points. Like the median, a centerpoint need not be one of the data points. Every non-empty set of points has at least one centerpoint.

**Kenneth Lee Clarkson** is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the *Journal of Computational Geometry*.

In computational geometry and computer science, the **minimum-weight triangulation** problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the **optimal triangulation**.

- 1 2 3 Toussaint, G. T. (1980), "The relative neighborhood graph of a finite planar set",
*Pattern Recognition*,**12**(4): 261–268, doi:10.1016/0031-3203(80)90066-7 . - ↑ Jaromczyk, J.W.; Toussaint, G.T. (1992), "Relative neighborhood graphs and their relatives",
*Proceedings of the IEEE*,**80**(9): 1502–1517, doi:10.1109/5.163414 . - ↑ Supowit, K. J. (1983), "The relative neighborhood graph, with an application to minimum spanning trees",
*J. ACM*,**30**(3): 428–448, doi:10.1145/2402.322386 . - ↑ Katajainen, Jyrki; Nevalainen, Olli; Teuhola, Jukka (1987), "A linear expected-time algorithm for computing planar relative neighbourhood graphs",
*Information Processing Letters*,**25**(2): 77–86, doi:10.1016/0020-0190(87)90225-0 . - 1 2 Jaromczyk, J. W.; Kowaluk, M. (1987), "A note on relative neighborhood graphs",
*Proc. 3rd Symp. Computational Geometry*, New York, NY, USA: ACM, pp. 233–241, doi:10.1145/41958.41983 . - ↑ Lingas, A. (1994), "A linear-time construction of the relative neighborhood graph from the Delaunay triangulation",
*Computational Geometry*,**4**(4): 199–208, doi:10.1016/0925-7721(94)90018-3 . - ↑ Jaromczyk, J. W.; Kowaluk, M. (1991), "Constructing the relative neighborhood graph in 3-dimensional Euclidean space",
*Discrete Appl. Math.*,**31**(2): 181–191, doi:10.1016/0166-218X(91)90069-9 . - ↑ Agarwal, Pankaj K.; Mataušek, Jiří (1992), "Relative neighborhood graphs in three dimensions",
*Proc. 3rd ACM–SIAM Symp. Discrete Algorithms*, pp. 58–65. - ↑ O'Rourke, J. (1982), "Computing the relative neighborhood graph in the
*L*_{1}and*L*_{∞}metrics",*Pattern Recognition*,**15**(3): 189–192, doi:10.1016/0031-3203(82)90070-X . - ↑ Lee, D. T. (1985), "Relative neighborhood graphs in the
*L*_{1}-metric",*Pattern Recognition*,**18**(5): 327–332, doi:10.1016/0031-3203(85)90023-8 . - ↑ Urquhart, R. B. (1980), "Algorithms for computation of relative neighborhood graph",
*Electronics Letters*,**16**(14): 556–557, doi:10.1049/el:19800386 . - ↑ Toussaint, G. T. (1980), "Comment: Algorithms for computing relative neighborhood graph",
*Electronics Letters*,**16**(22): 860, doi:10.1049/el:19800611 . Reply by Urquhart, pp. 860–861. - ↑ Andrade, Diogo Vieira; de Figueiredo, Luiz Henrique (2001), "Good approximations for the relative neighbourhood graph",
*Proc. 13th Canadian Conference on Computational Geometry*(PDF).

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.