Geodesic
Finite convergence into a convex polytope via facet reflections
Applications of Mathematics, Tome 68 (2023) no. 4, pp. 387-404

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

The problem of utilizing facet reflections to bring a point outside of a convex polytope to inside has not been studied explicitly in the literature. Here we introduce two algorithms that complete the task in finite iterations. The first algorithm generates multiple solutions on the plane, and can be readily utilized in creating games on a plane or as a level generation method for video games. The second algorithm is a new efficient way to bring infeasible starting points of an optimization problem to inside a feasible region defined by constraints. Using simulations, we demonstrate many desirable properties of the algorithm. Specifically, more edges do not lead to more iterations in $\mathbb {R}^2$, the algorithm is extremely efficient in high dimensions, and it can be employed to discretize the feasibility region using a grid of points outside the region.
DOI : 10.21136/AM.2022.0134-22
Classification : 52-08, 52B11, 52B12, 90C59
Keywords: convex geometry; optimization; infeasible start; strategy games 
@article{10_21136_AM_2022_0134_22,
     author = {Ekanayake, Dinesh B. and LaFountain, Douglas J. and Petracovici, Boris},
     title = {Finite convergence into a convex polytope via facet reflections},
     journal = {Applications of Mathematics},
     pages = {387--404},
     publisher = {mathdoc},
     volume = {68},
     number = {4},
     year = {2023},
     doi = {10.21136/AM.2022.0134-22},
     mrnumber = {4612739},
     zbl = {07729503},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.2022.0134-22/}
}
TY  - JOUR
AU  - Ekanayake, Dinesh B.
AU  - LaFountain, Douglas J.
AU  - Petracovici, Boris
TI  - Finite convergence into a convex polytope via facet reflections
JO  - Applications of Mathematics
PY  - 2023
SP  - 387
EP  - 404
VL  - 68
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.21136/AM.2022.0134-22/
DO  - 10.21136/AM.2022.0134-22
LA  - en
ID  - 10_21136_AM_2022_0134_22
ER  - 
%0 Journal Article
%A Ekanayake, Dinesh B.
%A LaFountain, Douglas J.
%A Petracovici, Boris
%T Finite convergence into a convex polytope via facet reflections
%J Applications of Mathematics
%D 2023
%P 387-404
%V 68
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.21136/AM.2022.0134-22/
%R 10.21136/AM.2022.0134-22
%G en
%F 10_21136_AM_2022_0134_22
Ekanayake, Dinesh B.; LaFountain, Douglas J.; Petracovici, Boris. Finite convergence into a convex polytope via facet reflections. Applications of Mathematics, Tome 68 (2023) no. 4, pp. 387-404. doi: 10.21136/AM.2022.0134-22

Cité par Sources :