31 research outputs found
Distribution-sensitive construction of the greedy spanner
No full textThe greedy spanner is the highest quality geometric spanner (in e.g. edge count and weight, both in theory and practice) known to be computable in polynomial time. Unfortunately, all known algorithms for computing it on n points take O(n 2) time, limiting its use on large data sets.
We observe that for many point sets, the greedy spanner has many ‘short’ edges that can be determined locally and usually quickly, and few or no ‘long’ edges that can usually be determined quickly using local information and the well-separated pair decomposition. We give experimental results showing large to massive performance increases over the state-of-the-art on nearly all tests and real-life data sets. On the theoretical side we prove a near-linear expected time bound on uniform point sets and a near-quadratic worst-case bound.
Our bound for point sets drawn uniformly and independently at random in a square follows from a local characterization of t-spanners we give on such point sets: we give a geometric property that holds with high probability on such point sets. This property implies that if an edge set on these points has t-paths between pairs of points ‘close’ to each other, then it has t-paths between all pairs of points.
This characterization gives a O(n log2 n log2 logn) expected time bound on our greedy spanner algorithm, making it the first subquadratic time algorithm for this problem on any interesting class of points. We also use this characterization to give a O((n¿+¿|E|) log2 n loglogn) expected time algorithm on uniformly distributed points that determines if E is a t-spanner, making it the first subquadratic time algorithm for this problem that does not make assumptions on E
Computing the greedy spanner in linear space
No full textThe greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner on n points use O(n^2) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices. We present a linear-space algorithm that computes the same spanner for points in R^d running in O(n^2 log^2n) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented.
Keywords: Geometric spanner; Dilation; Stretch factor; Greedy algorithm; Computational geometr
Computing the greedy spanner in linear space
No full textThe greedy spanner is a high-quality spanner: its total weight, edge count and maximal degree are asymptotically optimal and in practice significantly better than for any other spanner with reasonable construction time. Unfortunately, all known algorithms that compute the greedy spanner of n points use O(n2) space, which is impractical on large instances. To the best of our knowledge, the largest instance for which the greedy spanner was computed so far has about 13,000 vertices.
We present a O(n)-space algorithm that computes the same spanner for points in Rd running in O(n2 log2n) time for any fixed stretch factor and dimension. We discuss and evaluate a number of optimizations to its running time, which allowed us to compute the greedy spanner on a graph with a million vertices. To our knowledge, this is also the first algorithm for the greedy spanner with a near-quadratic running time guarantee that has actually been implemented
Distribution-sensitive construction of the greedy spanner
No full textThe greedy spanner is the highest quality geometric spanner (in e.g. edge count and weight, both in theory and practice) known to be computable in polynomial time. Unfortunately, all known algorithms for computing it on n points take time, limiting its applicability on large data sets. We propose a novel algorithm design which uses the observation that for many point sets, the greedy spanner has many ‘short’ edges that can be determined locally and usually quickly. To find the usually few remaining ‘long’ edges, we use a combination of already determined local information and the well-separated pair decomposition. We give experimental results showing large to massive performance increases over the state-of-the-art on nearly all tests and real-life data sets. On the theoretical side we prove a near-linear expected time bound on uniform point sets and a near-quadratic worst-case bound. Our bound for point sets drawn uniformly and independently at random in a square follows from a local characterization of t-spanners we give on such point sets. We give a geometric property that holds with high probability, which in turn implies that if an edge set on these points has t-paths between pairs of points ‘close’ to each other, then it has t-paths between all pairs of points. This characterization gives an expected time bound on our greedy spanner algorithm, making it the first subquadratic time algorithm for this problem on any interesting class of points. We also use this characterization to give an expected time algorithm on uniformly distributed points that determines whether E is a t-spanner, making it the first subquadratic time algorithm for this problem that does not make assumptions on E
Distribution-sensitive construction of the greedy spanner (extended abstract)
No full textThe greedy spanner is the highest quality geometric spanner (in e.g. edge count and weight, both in theory and practice) known to be computable in polynomial time. Unfortunately, all known algorithms for computing it take O(n^2) time, limiting its applicability on large data sets.
We observe that for many point sets, the greedy spanner has many ‘short’ edges that can be determined locally and usually quickly, and few or no ‘long’ edges that can usually be determined quickly using local information and the well-separated pair decomposition. We give experimental results showing large to massive performance increases over the state-of-the-art on nearly all tests and real-life data sets. On the theoretical side we prove a near-linear expected time bound on uniform point sets and a near-quadratic worst-case bound.
Our bound for point sets drawn uniformly and independently at random in a square follows from a local characterization of t-spanners we give on such point sets.
This characterization gives a O(n log^2 n log^2 log n) expected time bound on our greedy spanner algorithm, making it the first subquadratic time algorithm for this problem on any interesting class of points
Neotropical Bats: Estimating Species Diversity with DNA Barcodes
No full textPMCID: PMC3144236This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited
Hundreds of variants clustered in genomic loci and biological pathways affect human height
No full textMost common human traits and diseases have a polygenic pattern of inheritance: DNA sequence variants at many genetic loci influence the phenotype. Genome-wide association (GWA) studies have identified more than 600 variants associated with human traits(1), but these typically explain small fractions of phenotypic variation, raising questions about the use of further studies. Here, using 183,727 individuals, we show that hundreds of genetic variants, in at least 180 loci, influence adult height, a highly heritable and classic polygenic trait(2,3). The large number of loci reveals patterns with important implications for genetic studies of common human diseases and traits. First, the 180 loci are not random, but instead are enriched for genes that are connected in biological pathways (P = 0.016) and that underlie skeletal growth defects (P<0.001). Second, the likely causal gene is often located near the most strongly associated variant: in 13 of 21 loci containing a known skeletal growth gene, that gene was closest to the associated variant. Third, at least 19 loci have multiple independently associated variants, suggesting that allelic heterogeneity is a frequent feature of polygenic traits, that comprehensive explorations of already-discovered loci should discover additional variants and that an appreciable fraction of associated loci may have been identified. Fourth, associated variants are enriched for likely functional effects on genes, being over-represented among variants that alter amino-acid structure of proteins and expression levels of nearby genes. Our data explain approximately 10% of the phenotypic variation in height, and we estimate that unidentified common variants of similar effect sizes would increase this figure to approximately 16% of phenotypic variation (approximately 20% of heritable variation). Although additional approaches are needed to dissect the genetic architecture of polygenic human traits fully, our findings indicate that GWA studies can identify large numbers of loci that implicate biologically relevant genes and pathways
Making vision into power : Britain's acquisition of the world's first radar-based integrated air defence system 1935 - 1941
No full textThis thesis represents the first application of a current conceptual model of defence acquisition to analyse the historical process, the 1935 - 1941 British acquisition of an integrated air defence system pivoted upon the innovative technology of radar. For successful acquisition of a military capability, the model posits that balanced attention must be focused acoss eight 'lines of developmen' - not only equipment, but also doctrine and concepts, logistics, structures, personnel, organisation, training and information with an overarching requirement for interoperability. This thesis contrasts what turned out to be a successful acquisition, of radar to achive air interception capability by day in the Battle of Britain, with less successful acquisition, or radar to achieve the same capability at night, where an effective system arrived too late to ward off the Blitz. The results establish the validity of the model and its attendant lines of development concepts, and furnish new insights into acquisition processes and military history. Acquisition lessons are derived for the capability-based involvement of industry, for the experience and personality necessary for key managers at different 'life stages' of an acquisition and for the avoidance of over-rapid 'dysfunctional diffusion' of innovative technologies. Historical insights for the Battle of Britain include the sub-optimal performance, for trivial reasons, of key South Coast radars, and the critical importance of the human elements of the radar-based air defence system. For the Blitz, airborne radar hardware has previously been identified as a key problem, whereas research here exposes the greater need for accurate ground control radar, the sound selection and training of pilots and operators in new tactics, and provision of equipment maintainers and test gear. New evidence illustrates that pursuit of an alternative to radar significantly delayed the optimal solution, and throws fresh light both on personalities and on development process management
Progressive geometric algorithms
No full textProgressive algorithms are algorithms that, on the way to computing a complete solution to the problem at hand, output intermediate solutions that approximate the complete solution increasingly well. We present a framework for analyzing such algorithms, and develop efficient progressive algorithms for two geometric problems: computing the convex hull of a planar point set, and finding popular places in a set of trajectories
Riches, Poverty, and the Faithful: Perspectives on Wealth in the Second Temple Period and the Apocalypse of John
No full textThe present study considers the degree to which John’s portrayal of the faithful Christian community in the Apocalypse is informed by Jewish apocalyptic traditions related to wealth in the Second Temple period. Previous studies have attributed the author’s radical stance against wealth and economic participation to an ad hoc response against the idolatry and social injustices of the Roman Empire and imperial cults. This thesis argues that there is reasonable evidence to suggest that the author may have already been predisposed to reject affluence as a feature of the present age for the ideal faithful community based on received tradition.
The study begins by delineating the problem in a critical review of how scholars have attempted to deal with this language through either the social world of Roman Asia Minor or the author’s use of the biblical prophets. This discussion demonstrates the need to take a tradition-historical approach that includes an examination of Jewish apocalyptic traditions preserved among the Dead Sea Scrolls as well as other Jewish literature not found at Qumran that demonstrate a decided concern over wealth. These Second Temple texts are then examined collectively against the language of wealth and poverty in selected passages of the Apocalypse. The evidence reveals an emphasis on the part of John on the irreversible, eschatological consequences of ethical behaviour directly related to wealth based on a certain cosmological and theological understanding, an emphasis that has close analogies in some Second Temple literature.
The study concludes that traditions preserved in the Epistle of Enoch and later Enochic texts have played a formative role in shaping the author’s theological perspective concerning material blessing for the faithful in the present age and the world through which he legitimised the radical stance he imposed on his readers/hearers
