Блог пользователя usernameson

Does the convex hull trick work in 3 or more dimensions?
Автор usernameson, история, 6 лет назад, По-английски

Let's say we have a set of planes of the form zi = aix + biy + c. Each plane will have a (possibly empty) region of where it has the maximum z value over all the planes in the set. I am wondering if these regions have sufficiently nice properties that they can be maintained, updated and queried efficiently.

  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Yeah I guess so. The only property that is important is monotonicity. One important point to note here is that unlike the 2d version of the trick where only a single point is involved, a line should be the criterion for querying.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

In 3 dimensions, it is possible, but a bit tricky to implement and was discussed here. Queries and insertions run in . The basic idea in 3D is that you do scanline over one dimension and maintain a changing 2D-convex hull data structure. The scanline is computed by divide-and-conquer.

In d dimensions, the convex hull can have faces, so I wouldn't expect an efficient solution for d ≥ 4.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

i don't even know how it works in 2dimensions

→ Ответить