Revisions to On some optimal containers of a set of points on the 2D plane

Bumped by Community user

occurred Sep 26, 2021 at 19:04

Bumped by Community user

occurred May 29, 2021 at 19:00

edited tags

Link

edited Apr 29, 2021 at 17:25

RobPratt

5.4k
1
15
25

added 96 characters in body

Source Link

edited Jul 9, 2020 at 21:36

Nandakumar R

6k
3
7
20

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find

the smallest semicircular region (semidisk) that contains the points
the smallest circular segment that contains the points (2 variants - 'smallest' could mean either of 'least area' or 'least perimeter').
the smallest sector that contains the points (again, 2 variants)

I am not aware of previous works on these questions.

Note: An O(N^2) algorithm for question 1 has been proposed in https://arxiv.org/abs/2005.10245. No proof of optimality was given, so there could be faster algorithms.

Some thoughts on question 2 are also given there but no algorithm.

Higher dimensional analogs of these questions - hemisphere, spherical segment etc..- arise naturally.

Note added on July 6th 2020: Finding theNote: The question of finding largestthe largest semidisk/sector/circular segment contained in a given convex region C too seems unexplored. It is not hard to see that for a given C, the largest semidisk it contains should necessarily have both end points of the diameter on the boundary of C. How to useBased on this fact to form anproperty, a basic algorithm that finds the semidisk is not clear.(complexity estimate: O(N^4)) has been proposed at https://nandacumar.blogspot.com/2020/07/largest-semidisk-inside-convex-polygon.html

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find

the smallest semicircular region (semidisk) that contains the points
the smallest circular segment that contains the points (2 variants - 'smallest' could mean either of 'least area' or 'least perimeter').
the smallest sector that contains the points (again, 2 variants)

I am not aware of previous works on these questions.

Note: An O(N^2) algorithm for question 1 has been proposed in https://arxiv.org/abs/2005.10245. No proof of optimality was given, so there could be faster algorithms.

Some thoughts on question 2 are also given there but no algorithm.

Higher dimensional analogs of these questions - hemisphere, spherical segment etc..- arise naturally.

Note added on July 6th 2020: Finding the largest semidisk/sector/circular segment contained in a given convex region C too seems unexplored. It is not hard to see that for a given C, the largest semidisk it contains should necessarily have both end points of the diameter on the boundary of C. How to use this fact to form an algorithm that finds the semidisk is not clear.

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find

the smallest semicircular region (semidisk) that contains the points
the smallest circular segment that contains the points (2 variants - 'smallest' could mean either of 'least area' or 'least perimeter').
the smallest sector that contains the points (again, 2 variants)

I am not aware of previous works on these questions.

Note: An O(N^2) algorithm for question 1 has been proposed in https://arxiv.org/abs/2005.10245. No proof of optimality was given, so there could be faster algorithms.

Some thoughts on question 2 are also given there but no algorithm.

Higher dimensional analogs of these questions - hemisphere, spherical segment etc..- arise naturally.

Note: The question of finding the largest semidisk/sector/circular segment contained in a given convex region C too seems unexplored. It is not hard to see that for a given C, the largest semidisk it contains should necessarily have both end points of the diameter on the boundary of C. Based on this property, a basic algorithm (complexity estimate: O(N^4)) has been proposed at https://nandacumar.blogspot.com/2020/07/largest-semidisk-inside-convex-polygon.html

new class of questions raised

Source Link

edited Jul 6, 2020 at 6:55

Nandakumar R

6k
3
7
20

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find

the smallest semicircular region (semidisk) that contains the points
the smallest circular segment that contains the points (2 variants - 'smallest' could mean either of 'least area' or 'least perimeter').
the smallest sector that contains the points (again, 2 variants)

I am not aware of previous works on these questions.

Note: An O(N^2) algorithm for question 1 has been proposed in https://arxiv.org/abs/2005.10245. No proof of optimality was given, so there could be faster algorithms.

Some thoughts on question 2 are also given there but no algorithm.

Higher dimensional analogs of these questions - hemisphere, spherical segment etc..- arise naturally.

Note added on July 6th 2020: Finding the largest semidisk/sector/circular segment contained in a given convex region C too seems unexplored. It is not hard to see that for a given C, the largest semidisk it contains should necessarily have both end points of the diameter on the boundary of C. How to use this fact to form an algorithm that finds the semidisk is not clear.

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find

the smallest semicircular region (semidisk) that contains the points
the smallest circular segment that contains the points (2 variants - 'smallest' could mean either of 'least area' or 'least perimeter').
the smallest sector that contains the points (again, 2 variants)

I am not aware of previous works on these questions.

Note: An O(N^2) algorithm for question 1 has been proposed in https://arxiv.org/abs/2005.10245. No proof of optimality was given, so there could be faster algorithms.

Some thoughts on question 2 are also given there but no algorithm.

Higher dimensional analogs of these questions - hemisphere, spherical segment etc..- arise naturally.

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find

the smallest semicircular region (semidisk) that contains the points
the smallest circular segment that contains the points (2 variants - 'smallest' could mean either of 'least area' or 'least perimeter').
the smallest sector that contains the points (again, 2 variants)

I am not aware of previous works on these questions.

Note: An O(N^2) algorithm for question 1 has been proposed in https://arxiv.org/abs/2005.10245. No proof of optimality was given, so there could be faster algorithms.

Some thoughts on question 2 are also given there but no algorithm.

Higher dimensional analogs of these questions - hemisphere, spherical segment etc..- arise naturally.

Note added on July 6th 2020: Finding the largest semidisk/sector/circular segment contained in a given convex region C too seems unexplored. It is not hard to see that for a given C, the largest semidisk it contains should necessarily have both end points of the diameter on the boundary of C. How to use this fact to form an algorithm that finds the semidisk is not clear.