Se um ponto é um vértice do casco convexo

O exercício é

Dado um conjunto de pontos e um ponto . Decidir em de tempo, se P é um vértice do polígono convexo formado a partir de pontos de S .$S$$p$$O(n)$$p$$S$

O problema é que estou um pouco confuso com a complexidade do tempo $O(n)$ . A solução mais ingênua seria construir polígono convexo em $O(n\log n)$ e testar se $p$ é um dos vértices.

Dica: o ponto é um vértice do salão convexo se houver duas meias linhas dele, de modo que todos os pontos caiam dentro do ângulo criado por eles.$p$

Aqui está uma idéia para um algoritmo baseado nesta dica:

Projete um algoritmo com duas variáveis e (pontos de entrada). O algoritmo examinará cada um dos pontos de entrada e atualizará e para que todos os pontos verificados até agora caiam dentro da cunha .$q$$r$$q$$r$$\angle qpr$

O problema é encontrar uma linha que atravessa $p$ e tem todos os outros pontos em $S$de um lado. Este é um problema bidimensional de programação linear, para que possa ser resolvido em$O(n)$tempo usando algoritmos geométricos de livros didáticos . Mas deixe-me descrever uma solução independente.

---

Para simplificar a notação, traduza todos os pontos para que $p$ é a origem $(0,0)$, e deixar $Q = S\setminus\{p\}$. Então queremos determinar se existe um número real$m$ de modo que (1) $y < mx$ para todos $(x,y)\in Q$ ou (2) $y > mx$ para todos $(x,y)\in Q$. No primeiro caso,$p$ é um vértice do casco superior de $S$; no segundo caso,$p$ é um vértice do casco inferior de $S$. Vou descrever um algoritmo para o primeiro caso; o outro caso é simétrico.

Se algum ponto $Q$ encontra-se diretamente acima $p$ (ou seja, se algum ponto $Q$ tem coordenadas $(0,y)$ para alguns $y>0$), então $p$não pode ficar no casco superior. É fácil verificar esta condição em$O(n)$ Tempo.

Portanto, não assuma pontos $Q$ deite-se diretamente acima $p$. o$y$-axis splits $Q$ em dois subconjuntos $L$ (esquerda) e $R$(direita). Pontos em$L$ tem negativo $x$-coordenadas e aponta $R$ tem positivo $x$-coordenadas. (Pontos diretamente abaixo$p$não importa; apenas ignore-os.)

$$m_L = \min_{(x,y)\in L} \frac{y}{x}, \quad M_R = \max_{(x,y)\in R} \frac{y}{x}, \quad \text{and} \quad m = \frac{m_L + M_R}{2}.$$ Agora, existem três casos a serem considerados:

• E se $m_L < M_R$, então todos os pontos $Q$ está estritamente abaixo da linha $y = mx$, tão $p$ é um vértice do casco superior.

• E se $m_L = M_R$, então a linha $y=mx$ passa por um ponto em $L$ e um ponto em $R$e nenhum ponto $Q$está estritamente acima dessa linha. assim$p$ fica em uma borda do casco superior, mas não é um vértice.

• E se $m_L > M_R$, pelo menos um ponto em $L$ e pelo menos um ponto $R$ estão estritamente acima da linha $y=mx$. assim$p$ encontra-se estritamente abaixo do casco superior.

É fácil calcular $m_L$ e $M_R$ no $O(n)$Tempo. Na verdade, não precisamos calcular$m$.