172 research outputs found
Binary plane partitions with cells of bounded complexity
No full textAbstract Binary Plane Partitions with Cells of Bounded Complexity by Henrik Sarkssian A binary plane partition (BPP) for a set of disjoint line segments in Euclidean plane is a simple hierarchical decomposition of a convex cell in the plane into convex faces by partitioning along lines. Given a finite set of disjoint segments in a convex cell in R2, a BPP partitions the plane (and some of the line segments) along a line and recurses on the segments left or clipped in each of the regions created after partitioning. The generalization of BPP to higher dimensions is binary space partition (BSP) in which we are given disjoint objects in a convex cell, and we recursively partition this cell by hyper planes. The size of BSP is defined to be the number of fragments that the input objects are partitioned into.We show that to prove an asymptotic upper bound for the size of BSP, one can investigate equivalently the number of regions generated by partitioning or one can instead count the number of events where a segment is cut. Based on previous work by Dr. Csaba Toth it is known that a convex cell with n disjoint segments inside the cell admits a BSP of size O(nlnn/lnlnn), and this bound is the best possible [1,2]. In this thesis we investigate BSPs with the additional restriction that all cells have constant description complexity; typically these cells will be vertical trapezoid.Includes bibliographical references (pages 41-41)California State University, Northridge. Department of Mathematics
On Optimal Polyline Simplification using the Hausdorff and Fréchet Distance
No full textWe revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given epsilon>0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most epsilon. We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms perform compared to the optimum possible, also in the situation where the algorithms are given a considerably larger error threshold than epsilon. Furthermore, we show that computing an optimal simplification using the undirected Hausdorff distance is NP-hard. The same holds when using the directed Hausdorff distance from the input to the output polyline, whereas the reverse can be computed in polynomial time. Finally, to compute the optimal simplification from a polygonal line consisting of n vertices under the Fréchet distance, we give an O(kn^5) time algorithm that requires O(kn^2) space, where k is the output complexity of the simplification
On the Upward Planarity of Mixed Plane Graphs
No full textA mixed plane graph is a plane graph whose edge set is partitioned into a set of directed edges and a set of undirected edges. An orientation of a mixed plane graph G is an assignment of directions to the undirected edges of G resulting in a directed plane graph TeX . In this paper, we study the computational complexity of testing whether a given mixed plane graph G is upward planar, i.e., whether it admits an orientation resulting in a directed plane graph G such that G admits a planar drawing in which each edge is represented by a curve monotonically increasing in the y-direction according to its orientation.
Our contribution is threefold. First, we show that the upward planarity testing problem is solvable in cubic time for mixed outerplane graphs. Second, we show that the problem of testing the upward planarity of mixed plane graphs reduces in quadratic time to the problem of testing the upward planarity of mixed plane triangulations. Third, we exhibit linear-time testing algorithms for two classes of mixed plane triangulations, namely mixed plane 3-trees and mixed plane triangulations in which the undirected edges induce a forest
Bounds on the maximum multiplicity of some common geometric graphs
No full textWe obtain new lower and upper bounds for the maximum multiplicity of some weighted, and respectively non-weighted, common geometric graphs drawn on points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations.
(i) We present a new lower bound construction for the maximum number of triangulations a set of points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits Omega (8.65^n) different triangulations. This improves the bound Omega (8.48^n) achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al.
(ii) We present a new lower bound of Omega(11.97^n) for the number of non-crossing spanning trees of the double chain composed of two convex chains. The previous bound, Omega(10.42^n), stood unchanged for more than 10 years.
(iii) Using a recent upper bound of 30^n for the number of triangulations, due to Sharir and Sheffer, we show that n points in the plane in general position admit at most O(68.664^n) non-crossing spanning cycles.
(iv) We derive exponential lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). It was known that the number of longest non-crossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we obtain tight bounds for the number of longest and shortest tours. We give a combinatorial characterization of the longest tours, which leads to an O(n log n) time algorithm for computing them
Random Walks on Polytopes of Constant Corank
No full textWe show that the pivoting process associated with one line and n points in r-dimensional space may need Omega(log^r n) steps in expectation as n -> infty. The only cases for which the bound was known previously were for r <= 3. Our lower bound is also valid for the expected number of pivoting steps in the following applications: (1) The Random-Edge simplex algorithm on linear programs with n constraints in d = n-r variables; and (2) the directed random walk on a grid polytope of corank r with n facets
Agriculture and the transition to the market
No full textAgricultural sectors in Eastern and Central Europe are large so that changes in producer prices, farm employment, and land ownership affect substantial numbers of people. In the past, food in the region was politicized. For decades, governments of Eastern European countries and the USSR offered their citizens stable, subsidized food prices and a steadily improving diet in an effort to demonstrate the superiority of communism over capitalism. During the transition, the context has changed, but food remains politicized. Many consumers in the region are ill-prepared to pay the real costs of food, which are quite high. The task of reducing those costs will be difficult, involving restructuring of farms and fostering competition in processing and distribution. Management of the agricultural transition will affect the political sustainability of the process and influence agriculture's contribution to the growth of emerging market economies. Although the agricultural sector of Eastern and Central Europe is large, Soviet agriculture dwarfs it in its impact on the region and the world. A positive program to stop the decline in Soviet agriculture could contribute to economic growth and political stability. Failure to remedy the fundamental flaws in Soviet agriculture will speed the country's slide into poverty and ethnic turmoil - and undermine the efforts of Central and Eastern Europeans to succeed.Access to Markets,Environmental Economics&Policies,Economic Theory&Research,Agricultural Knowledge&Information Systems,Markets and Market Access
Graph-based time-space trade-offs for approximate near neighbors
No full textWe take a first step towards a rigorous asymptotic analysis of graph-based approaches for finding (approximate) nearest neighbors in high-dimensional spaces, by analyzing the complexity of (randomized) greedy walks on the approximate near neighbor graph. For random data sets of size on the -dimensional Euclidean unit sphere, using near neighbor graphs we can provably solve the approximate nearest neighbor problem with approximation factor in query time and space , for arbitrary satisfying \begin{align} (2c^2 - 1) \rho_q + 2 c^2 (c^2 - 1) \sqrt{\rho_s (1 - \rho_s)} \geq c^4. \end{align} Graph-based near neighbor searching is especially competitive with hash-based methods for small and near-linear memory, and in this regime the asymptotic scaling of a greedy graph-based search matches the recent optimal hash-based trade-offs of Andoni-Laarhoven-Razenshteyn-Waingarten [SODA'17]. We further study how the trade-offs scale when the data set is of size , and analyze asymptotic complexities when applying these results to lattice sieving
Paratenic hosts for the parasitic nematode Anguillicola crassus in Lake Balaton, Hungary
No full textA 1 yr study was conducted to determine which fish species may play a role in the life cycle of Anguillicola crassus in various habitats of Lake Balaton, Hungary. The prevalence and intensity of the larval infection of fish species acting as paratenic hosts was studied, and observations were made on the types of paratenic host reactions against larvae. With the exception of 1 species, all 20 fish species were infected by A. crassus larvae; however, the prevalence and intensity of infection varied widely. Six species (asp, white bream, Chinese rasbora, pike, river goby, European catfish), hitherto unreported as paratenic hosts, also proved to be infected by larvae in Lake Balaton. Of the 13 fish species examined in large numbers, ruffe and European catfish showed the highest prevalence of infection (100 %), followed by river goby (83 %), white bream (79 %) and bleak (68 %). Of these 13 fish species, ruffe showed the highest intensity of infection by live larvae (mean intensity: 39.3 3rd stage larvae, L3), followed by European catfish (mean number of live larvae: 26.9) and river goby (mean number of live larvae: 9.1). The mean number of live L3 in bleak, a species regarded as the principal food source for eels, was 4.1. Specimens containing only dead or both dead and live larvae were much more common in cyprinid fishes than in species belonging to other taxonomical entities. In these fish, the process of encapsulation and subsequent necrosis of live larvae could also be observed. With knowledge of the feeding habits of eels, it appears that bleak play the most important role in the transmission of anguillicolosis. Other intensively infected fish species (e.g. ruffe) may also contribute to massive infection of individual eels, even if they have a lower share in the eels' food structure
Rectilinear crossing numbers of complete graphs with specific nested sequence of convex hulls
No full textLet P be a set of n points in the plane. Draw all segments joining pairs of points in P. We are interested in the number of segment-intersections, or crossings, in such a drawing. For a fixed n, the problem of minimizing the number of crossings over all sets of n points in the plane is a famous unsolved problem in Combinatorial Geometry. Paul Turan posed the problem for complete bipartite graph because as a prisoner in a concentration camp, Turan’s job was to transport bricks using a railway system - the rail crossings made it extremely ineffective because the bricks would often fall. We consider a variation of Turan's problem. We classify all sets of n points into classes according to the sizes of their convex layers and consider the minimum number of crossings over sets within the same class. We bound the minimum number of crossings for every class with two convex layers finding its exact value when the inner layer has one or two points and a full classification of the optimal sets. We also give exact values of the minimum number of crossings for all classes with up to 8 points, and bounds for classes with 9 points.California State University, Northridge. Department of Mathematics.Includes bibliographical references (page 26
- …
