Mixing
Multiple use of Fermat's Principle , or Simple, Finite Tessellation (Unfolding)
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
First consider a specific question. Given a triangle and two interior points, a person at Point-1 is required to 'touch' all the 3 sides of the triangle exactly once and return to Point-2. Find the minimum possible distance he/she needs to travel to accomplish the given condition. Certainly, this is easily solved if one knows concepts like Fermat's Principle, Polygon Tessellation, etc. But it takes 12 (i.e. 2*n!, n=3) operations to find such path. (Basically, we Tessellate the figure to fit in a straight line across multiple images).
More General Question : Given an n-sided polygon and two interior points find such shortest distance. Clearly, this is easily found in 2*n! steps, i.e. O(n!). We see this isn't that efficient algorithm. Plus I have noticed that in total there are only n distinct path-lengths available for a polygon with n-sides.
More General Question : Consider closed, connected curve made up of several small curves (instead of straight line-segments as in above) and two interior points. Find such shortest distance traveled by a Person at Point-1 who touches all 'individual' small curves and returns to Point-2. (This is pretty unsolved for general cases - certainly we use the concept of reflection of light...but I don't know how complex this can go!)
I am interested in something faster than this (Tessellation/Multiple-Reflections which is taking O(n!) time) algorithm (for the polygonal problem). Please suggest improvements/different algorithms if you are aware of such a problem.
geometry optimization reflection tessellations
asked Jul 22 at 13:32
Amit Bendkhale
464
add a comment |Â
up vote
1
down vote
favorite
First consider a specific question. Given a triangle and two interior points, a person at Point-1 is required to 'touch' all the 3 sides of the triangle exactly once and return to Point-2. Find the minimum possible distance he/she needs to travel to accomplish the given condition. Certainly, this is easily solved if one knows concepts like Fermat's Principle, Polygon Tessellation, etc. But it takes 12 (i.e. 2*n!, n=3) operations to find such path. (Basically, we Tessellate the figure to fit in a straight line across multiple images).
More General Question : Given an n-sided polygon and two interior points find such shortest distance. Clearly, this is easily found in 2*n! steps, i.e. O(n!). We see this isn't that efficient algorithm. Plus I have noticed that in total there are only n distinct path-lengths available for a polygon with n-sides.
More General Question : Consider closed, connected curve made up of several small curves (instead of straight line-segments as in above) and two interior points. Find such shortest distance traveled by a Person at Point-1 who touches all 'individual' small curves and returns to Point-2. (This is pretty unsolved for general cases - certainly we use the concept of reflection of light...but I don't know how complex this can go!)
I am interested in something faster than this (Tessellation/Multiple-Reflections which is taking O(n!) time) algorithm (for the polygonal problem). Please suggest improvements/different algorithms if you are aware of such a problem.
geometry optimization reflection tessellations
asked Jul 22 at 13:32
Amit Bendkhale
464
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
First consider a specific question. Given a triangle and two interior points, a person at Point-1 is required to 'touch' all the 3 sides of the triangle exactly once and return to Point-2. Find the minimum possible distance he/she needs to travel to accomplish the given condition. Certainly, this is easily solved if one knows concepts like Fermat's Principle, Polygon Tessellation, etc. But it takes 12 (i.e. 2*n!, n=3) operations to find such path. (Basically, we Tessellate the figure to fit in a straight line across multiple images).
More General Question : Given an n-sided polygon and two interior points find such shortest distance. Clearly, this is easily found in 2*n! steps, i.e. O(n!). We see this isn't that efficient algorithm. Plus I have noticed that in total there are only n distinct path-lengths available for a polygon with n-sides.
More General Question : Consider closed, connected curve made up of several small curves (instead of straight line-segments as in above) and two interior points. Find such shortest distance traveled by a Person at Point-1 who touches all 'individual' small curves and returns to Point-2. (This is pretty unsolved for general cases - certainly we use the concept of reflection of light...but I don't know how complex this can go!)
I am interested in something faster than this (Tessellation/Multiple-Reflections which is taking O(n!) time) algorithm (for the polygonal problem). Please suggest improvements/different algorithms if you are aware of such a problem.
geometry optimization reflection tessellations
asked Jul 22 at 13:32
Amit Bendkhale
464
First consider a specific question. Given a triangle and two interior points, a person at Point-1 is required to 'touch' all the 3 sides of the triangle exactly once and return to Point-2. Find the minimum possible distance he/she needs to travel to accomplish the given condition. Certainly, this is easily solved if one knows concepts like Fermat's Principle, Polygon Tessellation, etc. But it takes 12 (i.e. 2*n!, n=3) operations to find such path. (Basically, we Tessellate the figure to fit in a straight line across multiple images).
More General Question : Given an n-sided polygon and two interior points find such shortest distance. Clearly, this is easily found in 2*n! steps, i.e. O(n!). We see this isn't that efficient algorithm. Plus I have noticed that in total there are only n distinct path-lengths available for a polygon with n-sides.
More General Question : Consider closed, connected curve made up of several small curves (instead of straight line-segments as in above) and two interior points. Find such shortest distance traveled by a Person at Point-1 who touches all 'individual' small curves and returns to Point-2. (This is pretty unsolved for general cases - certainly we use the concept of reflection of light...but I don't know how complex this can go!)
I am interested in something faster than this (Tessellation/Multiple-Reflections which is taking O(n!) time) algorithm (for the polygonal problem). Please suggest improvements/different algorithms if you are aware of such a problem.
geometry optimization reflection tessellations
asked Jul 22 at 13:32
Amit Bendkhale
464
edited Jul 22 at 13:37
asked Jul 22 at 13:32
Amit Bendkhale
464
asked Jul 22 at 13:32
Amit Bendkhale
464
asked Jul 22 at 13:32
Amit Bendkhale
464
464
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859402%2fmultiple-use-of-fermats-principle-or-simple-finite-tessellation-unfolding%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password