공간이 볼록인지 확인하는 알고리즘

다항식보다 적은 시간에 할 수 있습니까?공간이 볼록인지 확인하는 알고리즘

2009-06-09 l--' ' ' ' ' ' ---------' ' ' ' ' ' ' ' ' ' ' '

어떤 종류의? 어떤 범위 이상? 1 차 미분은 충분하지 않습니까? –

무엇의 다항식? 공간을 정의하는 점의 수? – AnnaR

나는 그가 메트릭 공간을 의미한다고 생각한다. 그래서 파생물로 어떻게 할 것인가? –

-2

음 ... 재미있는 질문입니다. 나는 대답이 '예'라고 믿는다. 대충 각 얼굴의 평면 방정식을 찾으십시오. 결합 된 모든면의 쌍에 대해 그 사이의 각도가 둔각이면 볼록한면이 오목합니다. 이것은 O (log (n)) 시간에 실행되어야합니다.

내가 그래프 착색 알고리즘을 사용하여이 운동의 몇 가지 방법이 셨을 텐데요,하지만 난 그냥 똑똑하지 않다 ... 공간

출처

2009-06-09 17:59:53

좋아,이 downvote받은 후 무엇입니까? –

다시 O (log (n))입니까? 당신은 각 비행기를 위해 그것을하고있다. – Yogi

@ Yogi : 무엇? 각면의 평면 방정식을 찾는 것은 O (1)이다. 그것은 결합 된 비행기의 쌍을 비교하기 때문에 O (log (n))입니다. 폴리곤에 대한 평면 방정식을 찾는 것은 일정 시간이므로 O (1)이므로 알고리즘의 전체 순서에는 영향을 미치지 않습니다. –

더 많은 단어를 사용하십시오.

정확히 무엇을 요구하는지 알 수 있습니다. 우리는 단지 추측 할 수 있습니다.

공간이 일반적으로 볼록하거나 오목 할 수 있다고 생각하지 않습니다. 아마도 볼륨 또는 면적을 의미할까요? 어쨌든 나는 표면의 복잡성이 본질적으로 다항식이 될 것이라는 점을 감안할 때 다항식 시간을 이길 것이라고 생각하지 않습니다.

출처

2009-06-09 17:54:22 Karl

공간이 볼록인지 확인하는 알고리즘

답변

관련 문제