We consider the problem of finding inscribed boxes and axis-aligned inscribed boxes of maximum volume, inside a compact and solid convex set. Our algorithms are capable of solving these two problems in any such set that can be represented with finite number of convex inequalities. For the axis-aligned case, we formulate the problem for higher dimensions and present an exact optimization algorithm which solves the problem in @math time, where @math is the dimension and @math is the number of inequalities defining the convex set. For the general case, after formulating the problem for higher dimensions we investigate the traditional 2-dimensional problem, which is in the literature merely considered for convex polygons, for a broad range of convex sets. We first present a new exact algorithm that finds the largest inscribed axis-aligned rectangle in such convex sets for any given direction of axes in @math time. Using this exact algorithm as a subroutine, we present an @math -approximation algorithm that computes @math -approximation to the largest inscribed rectangle with computational complexity of @math . Finally, we show that how this running time can be improved to @math with a @math pre-processing time when the convex set is a polygon.
Finding largest inscribed objects inside a polygon is not restricted to neither rectangles nor convex polygons. @cite_5 presented @math algorithms for finding inscribed equilateral triangle and square of maximum area inside a convex polygon and an @math algorithm for finding the largest inscribed equilateral triangle inside a general polygon. @cite_3 developed an @math algorithm for the problem of finding the largest empty rectangle among a point set. Jin proposed an @math algorithm @cite_31 and an @math algorithm @cite_33 for finding all locally maximal area parallelogram inside a convex polygon. Recently, @cite_23 showed that a long lasting linear time algorithm for finding the maximal triangle inside a convex polygon proposed in 1979 by Dobkin and Snyder back @cite_25 was in fact incorrect and then provided an @math algorithm for this problem. Later, Jin @cite_7 proposed another linear time algorithm for the problem of finding the largest triangle inside a convex polygon.
@cite_33 @cite_7 @cite_3 @cite_23 @cite_5 @cite_31 @cite_25
2560303642 2735102532 2046334944 2617996878 2765988383 2022366735
We revisit the following problem: Given a convex polygon @math , find the largest-area inscribed triangle. We show by example that the linear-time algorithm presented in 1979 by Dobkin and Snyder for solving this problem fails. We then proceed to show that with a small adaptation, their approach does lead to a quadratic-time algorithm. We also present a more involved @math time divide-and-conquer algorithm. Also we show by example that the algorithm presented in 1979 by Dobkin and Snyder for finding the largest-area @math -gon that is inscribed in a convex polygon fails to find the optimal solution for @math . Finally, we discuss the implications of our discoveries on the literature. We consider the problem of finding the maximum area parallelogram (MAP) inside a given convex polygon. Our main result is an algorithm for computing the MAP in an @math -sided polygon in @math time. Achieving this running time requires proving several new structural properties of the MAP. Our algorithm actually computes all the locally maximal area parallelograms (LMAPs). In addition to the algorithm, we prove that the LMAPs interleave each other, thus the number of LMAPs is bounded by @math . We discuss applications of our result to, among others, the problem of computing the maximum area centrally-symmetric convex body (MAC) inside a convex polygon, and the simplest case of the Heilbronn Triangle Problem. We study a class of optimization problems in polygons that seek to compute the "largest" subset of a prescribed type, e.g., a longest line segment ("stick") or a maximum-area triangle or convex body ("potato"). Exact polynomial-time algorithms are known for some of these problems, but their time bounds are high (e.g., O(n7) for the largest convex polygon in a simple n-gon). We devise efficient approximation algorithms for these problems. In particular, we give near-linear time algorithms for a (1 - ∈)-approximation of the biggest stick, an O(1)-approximation of the maximum-area convex body, and a (1 - ∈)-approximation of the maximum-area fat triangle or rectangle. In addition, we give efficient methods for computing large ellipses inside a polygon (whose vertices are a dense sampling of a closed smooth curve). Our algorithms include both deterministic and randomized methods, one of which has been implemented (for computing large area ellipses in a well sampled closed smooth curve). Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted. We consider the problem of finding the maximum area parallelogram (MAP) inside a given convex polygon. Our main result is an algorithm for computing the MAP in an n-sided polygon in O(n 2 ) time. Achieving this running time requires proving several new structural properties of the MAP, and combining them with a rotating technique of Toussaint [10]. We also discuss applications of our result to the problem of computing the maximum area centrallysymmetric convex body (MAC) inside a given convex polygon, and to a “fault tolerant area maximization” problem which we define. 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<1. We further give a deterministic approximation algorithm that computes an inscribed rectangle of area at least ([email protected]) times the optimum in running time O([email protected]^2logn) and show how this running time can be slightly improved. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . The goal of this paper is to show that the concept of the shortest path inside a polygonal region contributes to the design of efficient algorithms for certain geometric optimization problems involving simple polygons: computing optimum separators, maximum area or perimeter-inscribed triangles, a minimum area circumscribed concave quadrilateral, or a maximum area contained triangle. The structure for the algorithms presented is as follows: (a) decompose the initial problem into a low-degree polynomial number of optimization problems; (b) solve each individual subproblem in constant time using standard methods of calculus, basic methods of numerical analysis, or linear programming. These same optimization techniques can be applied to splinegons (curved polygons). First a decomposition technique for curved polygons is developed; this technique is substituted for triangulation in creating equally efficient curved versions of the algorithms for the shortest-path tree, ray-shooting, and two-point shortest path... We propose a novel geometric structure induced by any given convex polygon @math , called @math , which is an arrangement of @math segments, each of which is parallel to an edge of @math , where @math denotes the number of edges of @math . This structure enjoys six simple yet nontrivial properties, which can be derived from two elementary geometric properties -- convexity and parallelism. We then apply @math to solve the geometric optimization problem of computing the parallelogram(s) in @math with the maximum area. We show that the essential nature of the locally maximal area parallelograms is captured by @math and that computing all these parallelograms reduces to answering @math location queries on @math . We answer each of these queries in @math time, and thus obtain an @math time algorithm for this optimization problem. Our algorithm avoids an explicit construction of @math , which would take @math time. Given a polygon @math , for two points @math and @math contained in the polygon, their is the length of the shortest @math -path within @math . A of radius @math centered at a point @math is the set of points in @math whose geodesic distance to @math is at most @math . We present a polynomial time @math -approximation algorithm for finding a densest geodesic unit disk packing in @math . Allowing arbitrary radii but constraining the number of disks to be @math , we present a @math -approximation algorithm for finding a packing in @math with @math geodesic disks whose minimum radius is maximized. We then turn our focus on of @math and present a @math -approximation algorithm for covering @math with @math geodesic disks whose maximal radius is minimized. Furthermore, we show that all these problems are @math -hard in polygons with holes. Lastly, we present a polynomial time exact algorithm which covers a polygon with two geodesic disks of minimum maximal radius. Abstract This paper considers the geometric optimization problem of finding the Largest area axis-parallel Rectangle (LR) in an n-vertex general polygon. We characterize the LR for general polygons by considering different cases based on the types of contacts between the rectangle and the polygon. A general framework is presented for solving a key subproblem of the LR problem which dominates the running time for a variety of polygon types. This framework permits us to transform an algorithm for orthogonal polygons into an algorithm for non-orthogonal polygons. Using this framework, we show that the LR in a general polygon (allowing holes) can be found in O(n log2 n) time. This matches the running time of the best known algorithm for orthogonal polygons. References are given for the application of the framework to other types of polygons. For each type, the running time of the resulting algorithm matches the running time of the best known algorithm for orthogonal polygons of that type. A lower bound of time in Ω(n log n) is established for finding the LR in both self-intersecting polygons and general polygons with holes. The latter result gives us both a lower bound of Ω(n log n) and an upper bound of O(n log2 n) for general polygons. The widely known linear time algorithm for computing the maximum area triangle in a convex polygon was found incorrect recently by Keikha et. al.(arXiv:1705.11035). We present an alternative algorithm in this paper. Comparing to the only previously known correct solution, ours is much simpler and more efficient. More importantly, our new approach is powerful in solving related problems. We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with n vertices. We give exact algorithms that solve these problems in time O ( n 3 ) . We also give ( 1 - e ) -approximation algorithms that take time O ( e - 1 2 log ? n + e - 3 2 ) . Finite convex geometries are combinatorial structures. It follows from a recent result of M. Richter and L.G. Rogers that there is an infinite set @math of planar convex polygons such that @math with respect to geometric convex hulls is a locally convex geometry and every finite convex geometry can be represented by restricting the structure of @math to a finite subset in a natural way. An @math is a differentiable convex simple closed curve @math in the plane having an inscribed circle of radius @math and a circumscribed circle of radius @math such that the ratio @math is at least @math . Motivated by Richter and Rogers' result, we construct a set @math such that (1) @math contains all points of the plane as degenerate singleton circles and all of its non-singleton members are differentiable convex simple closed planar curves; (2) @math with respect to the geometric convex hull operator is a locally convex geometry; (3) as opposed to @math , @math is closed with respect to non-degenerate affine transformations; and (4) for every (small) positive @math and for every finite convex geometry, there are continuum many pairwise affine-disjoint finite subsets @math of @math such that each @math consists of almost-circles of accuracy @math and the convex geometry in question is represented by restricting the convex hull operator to @math . The affine-disjointness of @math and @math means that, in addition to @math , even @math is disjoint from @math for every non-degenerate affine transformation @math . We present an on-line strategy that enables a mobile robot with vision to explore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest watchman tour that could be computed off-line. Our analysis is doubly founded on a novel geometric structure called angle hull. Let D be a connected region inside a simple polygon, P. We define the angle hull of D, @math , to be the set of all points in P that can see two points of D at a right angle. We show that the perimeter of @math cannot exceed in length the perimeter of D by more than a factor of 2. This upper bound is tight. Constructive Solid Geometry (CSG) is a powerful way of describing solid objects for computer graphics and modeling. The surfaces of any primitive object (such as a cube, sphere or cylinder) can be approximated by polygons. Being abile to find the union, intersection or difference of these objects allows more interesting and complicated polygonal objects to be created. The algorithm presented here performs these set operations on objects constructed from convex polygons. These objects must bound a finite volume, but need not be convex. An object that results from one of these operations also contains only convex polygons, and bounds a finite volume; thus, it can be used in later combinations, allowing the generation of quite complicated objects. Our algorithm is robust and is presented in enough detail to be implemented. The geodesic center of a simple polygon is a point inside the polygon which minimizes the maximum internal distance to any point in the polygon. We present an algorithm which calculates the geodesic center of a simple polygon withn vertices in timeO(n logn). An X-ray probe through a polygon measures the length of intersection between a line and the polygon. This paper considers the properties of various classes of X-ray probes, and shows how they interact to give finite strategies for completely describing convex n-gons. It is shown that @math probes are sufficient to verify a specified n-gon, while for determining convex polygons @math X-ray probes are necessary and @math sufficient, with @math sufficient given that a lower bound on the size of the smallest edge of P is known. Abstract Let P be a simple polygon with n sides. This paper shows how to preprocess the polygon so that, given two query points p and q inside P , the length of the shortest path inside the polygon from p to q can be found in time O (log n ). The path itself must be polygonal and can be extracted in additional time proportional to the number of turns it makes. The preprocessing consists of triangulation plus a linear amount of additional work. We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m vertices, containing an obstacle in a form of a simple polygon with n vertices. We present an O(m+n) time algorithm finding the path, going around the obstacle, whose curvature is the smallest possible.