Largest inscribed rectangles in convex polygons
| Autor: | Christian Knauer, Lena Schlipf, Jens Ejbye Schmidt, Hans Raj Tiwary |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Inscribed square problem
Inscribed rectangles in polygons Largest area rectangle Rectilinear polygon Convex polygon Approximation algorithms Theoretical Computer Science Combinatorics Computational Theory and Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Largest empty rectangle Polygon Geometric algorithms Discrete Mathematics and Combinatorics Rectangle Rectangle method Inscribed figure MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Journal of Discrete Algorithms. 13:78-85 |
| ISSN: | 1570-8667 |
| DOI: | 10.1016/j.jda.2012.01.002 |
| Popis: | We consider approximation algorithms for the problem of computing an inscribed rectangle having largest area in a convex polygon on n vertices. If the order of the vertices of the polygon is given, we present a randomized algorithm that computes an inscribed rectangle with area at least ([email protected]) times the optimum with probability t in time O([email protected]) for any constant t |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect