Skip to main content
Theoretical Computer Science

Return to Question

Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Draw attention by Simd
Bounty Started worth 50 reputation by Simd
Tweeted twitter.com/#!/StackCSTheory/status/373826328090648577
Choose title and body that makes it more likely this will be found via search (to incorporate several different ways that people might search for this problem). Also add some more tags.
Source Link
edit approved Aug 31, 2013 at 4:02
D.W.
edit approved Aug 31, 2013 at 4:02
D.W.
  • 12.4k
  • 2
  • 36
  • 84

Intersection of Batch membership testing for convex shape and set of pointspolyhedron specified in vertex representation

I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the convex shape. Currently I just use an open source linear programming solver for each point independently with a constant objective function.

However this is quite slow even in 100 dimensions. Is there a way to use the fact that all the query points are known in advance to speed the process up?

Intersection of convex shape and set of points

I have a convex shape defined by a set of vertices. I also have a large set of points and I would like to test which are contained in the convex shape. Currently I just use an open source linear programming solver for each point independently with a constant objective function.

However this is quite slow even in 100 dimensions. Is there a way to use the fact that all the query points are known in advance to speed the process up?

Batch membership testing for convex polyhedron specified in vertex representation

I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the convex shape. Currently I just use an open source linear programming solver for each point independently with a constant objective function.

However this is quite slow even in 100 dimensions. Is there a way to use the fact that all the query points are known in advance to speed the process up?

Source Link
Simd
Simd
  • 3.9k
  • 21
  • 49

Intersection of convex shape and set of points

I have a convex shape defined by a set of vertices. I also have a large set of points and I would like to test which are contained in the convex shape. Currently I just use an open source linear programming solver for each point independently with a constant objective function.

However this is quite slow even in 100 dimensions. Is there a way to use the fact that all the query points are known in advance to speed the process up?