Some Questions on Oriented Convex Containers
Let me quickly record some questions on 'oriented convex containers' of points sets. This post continues this arxiv article:
https://arxiv.org/abs/1802.10447. Note: oriented containers have a well direction of symmetry - examples are isosceles triangles, rectangles, ellipses etc. and the figures mentioned below.
1. to find the smallest SEMICIRCLE that contains a given set of points on the plane (for this question, we could think of an O(N^3) algorithm)
2. the smallest SECTOR of a circle that contains a set of points
3. the smallest SEGMENT OF A CIRCLE (region broken off a disk by a chord) containing a set of points.
4. the smallest ELLIPSE containing a set of points
(all questions except 1 have a least area and least perimeter versions - and perhaps least diameter of container).
Remarks:
1. I gathered from Prof. O'Rourke that the smallest containing ellipse (question 4 above) - indeed ellipsoid in higher dimensions - is a well studied problem.
2. I have seen an incremental approach to finding smallest enclosing circle that has linear complexity (in David Mount's lecture notes on computational geometry) - it appears to depend on the property: "If points of the set to be contained are considered in some random sequence, if the ith point is not within the smallest circle containing the first i-1 points, then, the best circle including the ith point too necessarily passes through the ith point" . This property is seen not to hold for rectangular containers but might hold for semicircle containers (as per some experiments we tried). So, there could be ways of improving substantially from the O(N^3) algo I could think of for smallest semicircle containing N points.
Update (14h May 2020): As in https://arxiv.org/abs/1802.10447, we can ask for both circular segment and sector containers: Are there convex regions such that its minimum perimeter circular segment container (sector container) with the minimum perimeter has a different orientation than its minimum area circular segment container (sector container)?
Indications: It appears that for any convex region, its two optimal circular segment containers always have the same or parallel axes of symmetry. Not sure about sector containers.
Update ( 23rd May, 2020): A short doc on whatever I could do has been posted at https://arxiv.org/abs/2005.10245 and a discussion page on these matters is at https://mathoverflow.net/questions/361590/on-some-optimal-containers-of-a-set-of-points-on-the-2d-plane
Update (6th July 2020): Finding the largest halfdisk/sector/segment contained within a given convex region C also seems unexplored. It is not hard to show that such a largest semidisk has both end points of its diameter on the boundary of C. Beyond that, one does not yet have an algorithm.
1. to find the smallest SEMICIRCLE that contains a given set of points on the plane (for this question, we could think of an O(N^3) algorithm)
2. the smallest SECTOR of a circle that contains a set of points
3. the smallest SEGMENT OF A CIRCLE (region broken off a disk by a chord) containing a set of points.
4. the smallest ELLIPSE containing a set of points
(all questions except 1 have a least area and least perimeter versions - and perhaps least diameter of container).
Remarks:
1. I gathered from Prof. O'Rourke that the smallest containing ellipse (question 4 above) - indeed ellipsoid in higher dimensions - is a well studied problem.
2. I have seen an incremental approach to finding smallest enclosing circle that has linear complexity (in David Mount's lecture notes on computational geometry) - it appears to depend on the property: "If points of the set to be contained are considered in some random sequence, if the ith point is not within the smallest circle containing the first i-1 points, then, the best circle including the ith point too necessarily passes through the ith point" . This property is seen not to hold for rectangular containers but might hold for semicircle containers (as per some experiments we tried). So, there could be ways of improving substantially from the O(N^3) algo I could think of for smallest semicircle containing N points.
Update (14h May 2020): As in https://arxiv.org/abs/1802.10447, we can ask for both circular segment and sector containers: Are there convex regions such that its minimum perimeter circular segment container (sector container) with the minimum perimeter has a different orientation than its minimum area circular segment container (sector container)?
Indications: It appears that for any convex region, its two optimal circular segment containers always have the same or parallel axes of symmetry. Not sure about sector containers.
Update ( 23rd May, 2020): A short doc on whatever I could do has been posted at https://arxiv.org/abs/2005.10245 and a discussion page on these matters is at https://mathoverflow.net/questions/361590/on-some-optimal-containers-of-a-set-of-points-on-the-2d-plane
Update (6th July 2020): Finding the largest halfdisk/sector/segment contained within a given convex region C also seems unexplored. It is not hard to show that such a largest semidisk has both end points of its diameter on the boundary of C. Beyond that, one does not yet have an algorithm.
posted by R.Nandakumar @ 11:26 AM
0 comments
