| 词条 | Orthogonal convex hull |
| 释义 |
In geometry, a set {{math|K ⊂ Rn}} is defined to be orthogonally convex if, for every line {{mvar|L}} that is parallel to one of standard basis vectors, the intersection of {{mvar|K}} with {{mvar|L}} is empty, a point, or a single segment. The term "orthogonal" refers to corresponding Cartesian basis and coordinates in Euclidean space, where different basis vectors are perpendicular, as well as corresponding lines. Unlike ordinary convex sets, an orthogonally convex set is not necessarily connected. The orthogonal convex hull of a set {{math|S ⊂ Rn}} is the intersection of all connected orthogonally convex supersets of {{mvar|S}}. These definitions are made by analogy with the classical theory of convexity, in which {{mvar|K}} is convex if, for every line {{mvar|L}}, the intersection of {{mvar|K}} with {{mvar|L}} is empty, a point, or a single segment (interval). Orthogonal convexity restricts the lines for which this property is required to hold, so every convex set is orthogonally convex but not vice versa. For the same reason, the orthogonal convex hull itself is a subset of the convex hull of the same point set. A point {{mvar|p}} belongs to the orthogonal convex hull of {{mvar|S}} if and only if each of the closed axis-aligned orthants having {{mvar|p}} as apex has a nonempty intersection with {{mvar|S}}. The orthogonal convex hull is also known as the rectilinear convex hull, or, in two dimensions, the {{mvar|x}}//polygon">polygon with some degenerate edges connecting extreme vertices in each coordinate direction. For a discrete point set such as this one, all orthogonal convex hull edges are horizontal or vertical. In this example, the orthogonal convex hull is connected. AlgorithmsSeveral authors have studied algorithms for constructing orthogonal convex hulls: {{harvtxt|Montuno|Fournier|1982}}{{mvar|y}} convex hull of a set of {{mvar|x}}-{{mvar|y}} polygons | year = 1982}}.
| last1 = Nicholl | first1 = T. M. | last2 = Lee | first2 = D. T. | author2-link = Der-Tsai Lee | last3 = Liao | first3 = Y. Z. | last4 = Wong | first4 = C. K. | doi = 10.1007/BF01933620 | journal = BIT | pages = 456–471 | title = On the X-Y convex hull of a set of X-Y polygons | volume = 23 | year = 1983 | issue = 4}}.
| last = O'Rourke | first = Joseph | author-link = Joseph O'Rourke (professor) | pages = 107–109 | publisher = Cambridge University Press | title = Computational Geometry in C | year = 1993}}.
| last1 = Ottmann | first1 = T. | last2 = Soisalon-Soininen | first2 = E. | last3 = Wood | first3 = Derick | author3-link = Derick Wood | doi = 10.1016/0020-0255(84)90025-2 | journal = Information Sciences | pages = 157–171 | title = On the definition and computation of rectilinear convex hulls | volume = 33 | year = 1984 | issue = 3}}.
| last = Rawlins | first = G. J. E. | publisher = University of Waterloo | series = Ph.D. thesis and Tech. Rep. CS-87-57 | title = Explorations in Restricted-Orientation Geometry | year = 1987}}.
| last1 = Rawlins | first1 = G. J. E. | last2 = Wood | first2 = Derick | author2-link = Derick Wood | doi = 10.1016/0890-5401(87)90045-9 | journal = Information and Computation | pages = 150–166 | title = Optimal computation of finitely oriented convex hulls | volume = 72 | year = 1987 | issue = 2}}.
| last1 = Rawlins | first1 = G. J. E. | last2 = Wood | first2 = Derick | author2-link = Derick Wood | contribution = Ortho-convexity and its generalizations | editor-last = Toussaint | editor-first = Godfried T. | editor-link = Godfried Toussaint | pages = 137–152 | publisher = Elsevier | title = Computational Morphology | year = 1988}}. 1 : Convex hulls |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。