Timeline for Testing if a point is inside a convex polytope formed by halfspaces in n-dimension
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 9, 2019 at 23:10 | review | Close votes | |||
| May 12, 2019 at 15:57 | |||||
| Oct 14, 2015 at 8:52 | comment | added | Zsbán Ambrus | See also cstheory.stackexchange.com/q/32804/8067 Inclusion of polytopes | |
| Sep 28, 2015 at 0:40 | comment | added | rajaditya_m | @JosephO'Rourke : That looks interesting. I will refernece it | |
| Sep 28, 2015 at 0:40 | comment | added | rajaditya_m | @F_G : That will involve a matrix multiplication which will be time-consuming for hidim data. I was hoping for a smaller time inequality check. Sorry if I have misunderstood the problem. | |
| Sep 24, 2015 at 7:40 | comment | added | F_G | Why not simply plug the value of $x$ in those $k$ inequalities ? | |
| Sep 23, 2015 at 16:13 | comment | added | Joseph O'Rourke | If you construct a Dobkin-Kirpatrick hierarchical data structure for the polytope of $m$ vertices, then point location can be accomplished in $O(\log m)$ time per query. | |
| Sep 23, 2015 at 15:54 | comment | added | Tony Huynh | You have already written your problem as a linear program. The Simplex Method does not care whether your polyhedron is bounded or not. | |
| Sep 23, 2015 at 15:33 | review | First posts | |||
| Sep 23, 2015 at 18:52 | |||||
| Sep 23, 2015 at 15:31 | history | asked | rajaditya_m | CC BY-SA 3.0 |