If we have a convex polyhedron with vertices $\mathbf{V}$ and project it on a plane $\mathbf{P}$, is this procedure equivalent to projecting points in $\mathbf{V}$ on the plane $\mathbf{P}$ and then computing the 2D convex hull of the projected vertices? In other words, is the projection of a convex polyhedron on a plane a convex polygon? If so, how we can prove it mathematically?
[Math] Is projection of a convex polyhedron on a plane a convex polygon
convex-analysispolyhedra
Related Solutions
Create a Voronoi diagram then, using edges of the Voronoi regions, create a binary decision tree with depth $O(\ln n)$ to determine the region in which each query point lies.
You can do better if you are willing to spend memory. Find a boundary circle where all the regions outside of it are radial, i.e. they look like a WWII Japanese flag and any ray from the origin intersects at most 2 of them. For query points within the circle, subdivide the area into a grid of squeares, each small enough so that only $O(1)$ work is required to determine which region the point lies within. For points outside the circle, similarly subdivide the angles into small enough radial regions such that each region intersects with only 2 Voronoi regions.
Then the algorithm becomes this:
- Is $q$ within the circle? If so, goto 4.
- Calculate
angle = atan2(q.y, q.x), thenradial_region_idx = (pi + angle) * num_radial_regions / (2 pi) - Use radial_region_idx to look up the answer or the boundary between the two voronoi regions. After $O(1)$ work we know which Voronoi region we're in. End.
- Calculate
x_idx = floor(q.x / dx)andy_idx = floor(q.y / dy). - Look up the record for tile
(x_idx,y_idx), perform $O(1)$ work, and we know which region we're in. End.
The convex hull of a subset $S$ of the plane is the smallest convex set that contains all of them. If $S$ is finite, this is a convex polygon whose vertices form some subset of $S$.
In your case, the points look like
Start from, say, the highest point $P_4$, which must be one of the vertices of the convex hull (it wouldn't be in the convex hull of lower points). Think of a line through $P_4$ that starts out horizontal and pivots clockwise. The first point it hits will be $P_7$, so that's the next point of your polygon.
Draw the line segment $P_4, P_7$. This will be an edge of your polygon. Now pivot the line, still clockwise, around $P_7$. The next point it hits will be $P_8$.
Draw the segment $P_7, P_8$, and continue in this way until you come back to $P_4$. And there's your convex hull.
Best Answer
Hint: A set $\mathbf{P}$ is convex iff for any points $x,y\in \mathbf{P}$ the segment $[x,y]$ joining them belongs to $\mathbf{P}$.