Finding minimum areak-gons

Given a setP ofn points in the plane and a numberk, we want to find a polygon with vertices inP of minimum area that satisfies one of the following properties: (1) is a convexk-gon, (2) is an empty convexk-gon, or (3) is the convex hull of exactlyk points ofP. We give algorithms for solving each of these three problems in timeO(kn ³). The space complexity isO(n) fork=4 andO(kn ²) fork5. The algorithms are based on a dynamic programming approach. We generalize this approach to polygons with minimum perimeter, polygons with maximum perimeter or area, polygons containing the maximum or minimum number of points, polygons with minimum weight (for some weights added to vertices), etc., in similar time bounds.This paper includes work done while David Eppstein was at Columbia University, Department of Computer Science, and while Günter Rote and Gerhard Woeginger were at the Freie Universität Berlin, Fachbereich Mathematik, Institut für Informatik. Research was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).     

A novel synthetic approach towards pyrazole-4-carboxamides using N-(3-(dimethylamino)-2-formylacryloyl)formamide

Abstract  

A novel synthesis of pyrazole-4-carboxamides is reported. The reaction of N-(3-(dimethylamino)-2-formylacryloyl)formamide, an intermediate obtained by Vilsmeier–Haack formylation of acetonitrile, with hydrazine hydrate or monosubstituted hydrazines provides such compounds in good yields. This method has advantages over other methods for construction of such ring systems previously described in the literature.     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

RP-LC and HPTLC Methods for the Determination of Olmesartan Medoxomil and Hydrochlorothiazide in Combined Tablet Dosage Forms

Two new, rapid, precise, accurate and specific chromatographic methods were described for the simultaneous determination of olmesartan medoxomil and hydrochlorothiazide in combined tablet dosage forms. The first method was based on reversed phase liquid chromatography using an Eurosphere 100 RP C18 column (250 × 4.6 mm ID, 5 μm). The mobile phase was methanol–0.05% o-phosphoric acid (60:40 v/v) at a flow rate of 1.0 mL min^?1. Commercially available tablets and laboratory mixtures containing both drugs were assayed and detected using a UV detector at 270 nm. The second method involved silica gel 60 F₂₅₄ high performance thin layer chromatography and densitometric detection at 254 nm using acetonitrile–ethyl acetate–glacial acid (7:3:0.4 v/v/v) as the mobile phase. Calibration curves ranged between 200–600 and 125–375 ng spot^?1 for olmesartan and hydrochlorothiazide, respectively.     

Spherically symmetric inhomogeneous dust collapse in higher dimensional space-time and cosmic censorship hypothesis

We consider a collapsing spherically symmetric inhomogeneous dust cloud in higher dimensional space-time. We show that the central singularity of collapse can be a strong curvature or a weak curvature naked singularity depending on the initial density distribution.     

A Central Limit Theorem for Convex Chains in the Square

Points P ₁ ,... ,P _n in the unit square define a convex n -chain if they are below y=x and, together with P ₀ =(0,0) and P _n+1 =(1,1) , they are in convex position. Under uniform probability, we prove an almost sure limit theorem for these chains that uses only probabilistic arguments, and which strengthens similar limit shape statements established by other authors. An interesting feature is that the limit shape is a direct consequence of the method. The main result is an accompanying central limit theorem for these chains. A weak convergence result implies several other statements concerning the deviations between random convex chains and their limit. Received April 17, 1998, and in revised form December 4, 1998.     

Triangulations intersect nicely

We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimum-weight triangulation which can be computed in polynomial time by matching and network-flow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation.