2006-01-01
Optimal polygon placement
Publication
Publication
Presented at the
18th Annual Canadian Conference on Computational Geometry, CCCG 2006 (August 2006), Kingston
Given a simple polygon P with m vertices and a set S of n points in the plane, we consider the problem of finding a rigid motion placement of P that contains the maximum number of points in S. We present two solutions to this problem that represent time versus space tradeoffs. The first algorithm runs in O(n3m3) expected time using O(n2m2) space. The second algorithm runs in O(n3m3 log(nm)) deterministic time and O(nm) space. While these algorithms represent a substantial improvement in the time bounds of previous work the main contribution is that the approach is extendible to related rigid motion placement problems including polygonal annulus placement.
| Additional Metadata | |
|---|---|
| Conference | 18th Annual Canadian Conference on Computational Geometry, CCCG 2006 |
| Citation |
Bose, P, & Morrison, J. (Jason). (2006). Optimal polygon placement. In Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006 (pp. 89–92).
|