직교 볼록 선체

점 세트의 직교 볼록 선체

기하학에서 $집합$ K ve^d R은 표준 기준 벡터 중 하나에 평행한 모든 선 $L$ 에 $대해$ K와 $L$ 의 교차점이 비어 있거나 점 또는 단일 세그먼트가 있는 경우 직교 볼록으로 정의된다."직교"라는 용어는 서로 다른 기본 벡터가 수직인 유클리드 공간에서 대응하는 데카르트적 기반과 좌표를 의미하며, 그에 상응하는 선도 의미한다.일반 볼록 세트와 달리 직교 볼록 세트가 반드시 연결되는 것은 아니다.

세트 $K$ ⊂ $R$ 의^d 직교 볼록 선체는 $K$ 의 모든 직교 볼록 대위의 교차점이다.

이러한 정의는 모든 $L$ 선에 $대해$ $L$ 과 K의 교차점이 비어 있거나 점 또는 단일 구간인 경우 $K$ 가 볼록한 고전적 볼록성 이론과 유추하여 이루어진다.직교 볼록도는 이 특성이 고정되어야 하는 선을 제한하므로, 모든 볼록 세트는 직교 볼록하지만 그 반대의 경우는 아니다.같은 이유로 직교 볼록 선체 자체는 같은 지점 세트의 볼록 선체의 부분집합이다. $p$ 지점은 $p$ 를 정점으로 하는 각각의 닫힌 축 정렬 직교량이 $K$ 와 비빈 교차점을 갖는 경우에만 $K$ 의 직교 볼록 선체에 속한다.

직교 볼록 선체는 직교 볼록 선체 또는 2차원에서 $x-y$ 볼록 선체로도 알려져 있다.

예

그림에는 평면과 직교 볼록 선체의 16개 점 세트가 표시된다.그림에서 볼 수 있듯이 직교 볼록 선체는 각 좌표 방향에서 극한 정점을 연결하는 일부 퇴보된 가장자리가 있는 다각형이다.이와 같은 이산형 점 세트의 경우 모든 직교 볼록 선체의 가장자리는 수평 또는 수직이다.이 예에서는 직교 볼록 선체가 연결된다.

대체 정의

비행기의 6점 세트.고전적인 정형외과-콘벡스 헐은 스스로 설정한 포인트다.

상단 그림의 포인트 세트의 Maximal Ortho-convex Hull.포인트 세트와 컬러 면적에 의해 형성된다.

상단 그림의 포인트 세트의 연결된 Ortho-convex Hul.포인트 세트, 컬러 영역 및 두 개의 정형-콘벡스 폴리곤 체인에 의해 형성된다.

상단 그림의 포인트 세트의 Functional Ortho-convex Hul.점 세트, 색 영역, 4선 세그먼트에 의해 형성된다.

볼록 선체에 대한 몇 가지 동등한 정의가 존재하는 고전적인 볼록도와는 대조적으로 볼록 선체의 정의와 유사하게 만들어진 직교 볼록 선체의 정의는 다른 기하학적 물체를 야기한다.지금까지 연구자들은 세트 $K\subset \mathbb {R} ^{d}$ $K\subset \mathbb {R} ^{d}$ $K\subset \mathbb {R} ^{d}$ $K\subset \mathbb {R} ^{d}$ ${\$ 의 직교 볼록 선체에 대한 다음의 네 가지 정의를 탐구했다 $K\subset \mathbb {R} ^{d}$

최대 정의:이 글의 소개에 설명된 정의.포인트 세트의 Maxima를 기반으로 한다.
고전적 정의: $K$ $K$ 의 직교 볼록 선체는 $K$ ${\displaystyle$ K $K$ Ottmann, Soisalon-Soinen & Wood(1984)의 모든 직교 볼록 대위의 교차점이다 $K$ .
연결된 정의: $K$ $K$ 의 직교 볼록 선체는 $K$ ${\displaystyle$ K $K$ Nicholl et al. (1983) 중 가장 작은 직교 볼록 대위로 연결된 것이다 $K$ .
기능 정의: $K$ $K$ 의 직교 볼록 선체는 $K$ ${\displaystyle K$ 마투셰크 & 플레차치(1998)에 $0$ 0 $[\displaystyle 0}$ 인 모든 비 음의 직교 볼록 함수의 0 집합의 교차점이다 $K$ .

오른쪽 그림에서 맨 위 그림에는 평면 내 6개 점 세트가 표시한다.점 세트의 고전적인 직교 볼록 선체는 점 세트 그 자체다.위에서 아래로 두 번째부터 네 번째까지의 그림은 각각 포인트 세트의 최대, 연결, 기능직교 볼록 선체를 보여준다.직교 볼록 선체는 일부 퇴보된 "에지"가 있는 다각형, 즉 내부 각도가 $˚{\$ 스타일 $90^{\circle$ }인 $90^{\circ }$ 직교 볼록한 다각형 체인이 극한 정점을 연결하는 $90^{\circ }$ 것이다.

고전 직교 볼록 선체

The classical orthogonal convex hull can be equivalently defined as the smallest orthogonally convex superset of a set $K\subset \mathbb {R} ^{2}$ , by analogy to the following definition of the convex hull: the convex hull of $K$ is the smallest convex superset of $K$ . 고전적인 직교 볼록 선체가 분리될 수 있다.점 집합에 표준 기준 벡터 중 하나에 평행한 선상에 점 쌍이 없는 경우, 해당 점 집합의 고전적인 직교 볼록 선체는 점 집합 자체와 동일하다.

볼록한 선체의 잘 알려진 성질은 카라테오도리의 정리로부터 유래한다.A point $x\in \mathbb {R} ^{d}$ is in the interior of the convex hull of a point set $K\subset \mathbb {R} ^{d}$ if, and only if, it is already in the convex hull of $d+1$ or fewer points of $K$ . This property is also valid f또는 고전적인 직교 볼록 선체.

연결된 직교 볼록 선체

정의상 연결된 직교 볼록 선체는 항상 연결되어 있다.하지만, 이것은 독특하지 않다.예를 들어 수평선이나 수직선에 놓여 있지 않은 평면의 점 쌍을 생각해 보십시오.이러한 지점의 연결된 직교 볼록 선체는 지점을 연결하는 $90^{\circ }$ 내부 각도가 $90^{\circ }$ ${\$ 인 직교 볼록형 다각형 교차 체인이다.그러한 모든 다각형 체인은 길이가 같기 때문에 점 세트에 대해 연결된 직교 볼록 선체가 무한히 많다.

평면의 점 세트의 경우 연결된 직교 볼록 선체를 최대 직교 볼록 선체로 쉽게 구할 수 있다.If the maximal orthogonal convex hull of a point set $K\subset \mathbb {R} ^{2}$ is connected, then it is equal to the connected orthogonal convex hull of $K$ . If this is not the case, then there are infinitely many connected orthogonal convex hulls for $K$ , and each 내부 각도가 $90^{\circ }$ ${\$ 90 $^{\circle$ }인 직교대 볼록형 다각형 체인과 ${\displaystyle$ K}의 최대 직교 볼록 선체의 연결된 구성요소를 결합하면 얻을 수 있다 $90^{\circ }$

기능성 직교 볼록 선체

기능직교 볼록 선체는 세트의 특성이 아니라 세트에 대한 기능의 특성을 사용하여 정의된다.즉, 다음과 같이 볼록함수의 개념을 제한한다.함수 $f:\mathbb {R} ^{d}\rightarrow \mathbb {R}$ : $f:\mathbb {R} ^{d}\rightarrow \mathbb {R}$ $f:\mathbb {R} ^{d}\rightarrow \mathbb {R}$ → $f:\mathbb {R} ^{d}\rightarrow \mathbb {R}$ ${\$ f $:\mathb$ { $R}$ ^{d}\ $오른쪽$ 화살표 $\mathb {R}}$ 은(는) 표준 기준 벡터의 0이 아닌 것과 평행하는 각 선에 대한 제한이 볼록함수라면 직교 볼록이라고 한다 $f:\mathbb {R} ^{d}\rightarrow \mathbb {R}$ .

알고리즘

여러 저자들이 직교 볼록 선체를 구성하는 알고리즘을 연구했다: Montuno & Fournier; Nicholl et al. (1983); Ottmann, Soisalon-Soinen & Wood; Karlsson & Overmars (1988);이러한 저자의 결과에 의해 평면에 $있는$ n개의 점의 직교 볼록 선체는 $시간$ $O$ ( $n$ $log$ n)로 구성될 수 있으며 $,$ 정수 좌표가 있는 점에 대한 정수 검색 데이터 구조를 사용하여 더 빠르게 구성될 수 있다.

참조

Biswas, Arindam; Bhowmick, Partha; Sarkar, Moumita; Bhattacharya, Bhargab B. (2012), "A Linear-time Combinatorial Algorithm to Find the Orthogonal Hull of an Object on the Digital Plane", Information Sciences, 216: 176–195, doi:10.1016/j.ins.2012.05.029.
Fink, Eugene; Wood, Derick (1996), "Fundamentals of restricted-orientation convexity" (PDF), Information Sciences, 92 (1–4): 175–196, doi:10.1016/0020-0255(96)00056-4.
Fink, Eugene; Wood, Derick (1998), "Generalized halfspaces in restricted-orientation convexity" (PDF), Journal of Geometry, 62 (1–2): 99–120, doi:10.1007/BF01237603, S2CID 14709697.
Karlsson, Rolf G.; Overmars, Mark H. (1988), "Scanline algorithms on a grid", BIT, 28 (2): 227–241, doi:10.1007/BF01934088, hdl:1874/16270, S2CID 32964283.
Matoušek, J.; Plecháč, P. (1998), "On Functional Separately Convex Hulls", Discrete & Computational Geometry, 19 (1): 105–130, doi:10.1007/PL00009331.
Montuno, D. Y.; Fournier, A. (1982), Finding the $x$ - $y$ convex hull of a set of $x$ - $y$ polygons, Technical Report 148, University of Toronto.
Nicholl, T. M.; Lee, D. T.; Liao, Y. Z.; Wong, C. K. (1983), "On the X-Y convex hull of a set of X-Y polygons", BIT, 23 (4): 456–471, doi:10.1007/BF01933620, S2CID 10492640.
O'Rourke, Joseph (1993), Computational Geometry in C, Cambridge University Press, pp. 107–109.
Ottmann, T.; Soisalon-Soininen, E.; Wood, Derick (1984), "On the definition and computation of rectilinear convex hulls", Information Sciences, 33 (3): 157–171, doi:10.1016/0020-0255(84)90025-2.
Rawlins, G. J. E. (1987), Explorations in Restricted-Orientation Geometry, Ph.D. thesis and Tech. Rep. CS-87-57, University of Waterloo.
Rawlins, G. J. E.; Wood, Derick (1987), "Optimal computation of finitely oriented convex hulls", Information and Computation, 72 (2): 150–166, doi:10.1016/0890-5401(87)90045-9.
Rawlins, G. J. E.; Wood, Derick (1988), "Ortho-convexity and its generalizations", in Toussaint, Godfried T. (ed.), Computational Morphology, Elsevier, pp. 137–152.

Search