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.
To our knowledge, except Amenta's model @cite_28 for LIAR and the model of @cite_22 for LIR, no other optimization based algorithm published so far for these two problems. Again, except Amenta's model for LIAR @cite_28 , we are not aware of any model or algorithm for the higher dimension problem. Our optimization model for LIAR is much more efficient than Amenta's model. Also none of the algorithms in the literature are able to solve both problems, while our parametric approach is able to do so in 2-dimensional case. Moreover, except 's algorithm @cite_22 , no algorithm is published so far for either of these problems that is capable of dealing with other geometric convex sets such as ellipses and not just polygons. In 's algorithm @cite_22 it is not clear whether those two queries are doable for any convex set and if yes what would @math be in their algorithm's running time. Our algorithm is unique in the sense that its performance depends to the number of inequalities defining a convex set, e.g. while for a polygon this is @math for an ellipse this is one.
@cite_28 @cite_22
2048733643 1688647404
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 . A set L@?V(G) of a graph G=(V,E) is a liar's dominating set if (1) for all v@?V(G), |N"G[v]@?L|>=2 and (2) for every pair u,v@?V(G) of distinct vertices, |(N"G[u]@?N"G[v])@?L|>=3. A graph G=(V,E) admits a liar's dominating set if each of its connected component has at least three vertices. Given a graph G=(V,E) and an integer K, the liar's domination decision problem (LR-DOMDP) is to decide whether G has a liar's dominating set of cardinality at most K. Slater [P.J. Slater, Liar's Domination, Networks, 54(2) (2009) 70-74] proved that the LR-DOMDP is NP-complete for general graphs. Subsequently, Roden and Slater [M.L. Roden and P.J. Slater, Liar's domination in graphs, Discrete Math., 309(19) (2009) 5884-5890] showed a more general family of problems to each be NP-complete for bipartite graphs. Besides this result, no other algorithmic result for the liar's dominating set problem is available in the literature. In this paper, we first strengthen the complexity result of the LR-DOMDP by showing that this problem remains NP-complete for split graphs and hence for chordal graphs. Finally, we propose a linear time algorithm for computing a minimum cardinality liar's dominating set in a tree.