TY - JOUR
AB - Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many spherical balls in R(d) These algorithms are based on a simplicial complex dual to a decomposition of the union of balls using Voronoi cells, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in R(3) where unions of finitely many balls are commonly used as models of molecules.
AU - Herbert Edelsbrunner
ID - 4028
IS - 1
JF - Discrete & Computational Geometry
TI - The union of balls and its dual shape
VL - 13
ER -
TY - JOUR
AB - A general and direct method for computing the Betti numbers of a finite simplicial complex in Bd is given. This method is complete for d less than or equal to 3, where versions of this method run in time O(n alpha(n)) and O(n), n the number of simplices. An implementation of the algorithm is applied to alpha shapes, which is a novel geometric modeling tool.
AU - Delfinado, Cecil J
AU - Herbert Edelsbrunner
ID - 4029
IS - 7
JF - Computer Aided Geometric Design
TI - An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere
VL - 12
ER -
TY - CONF
AB - Any arbitrary polyhedron P contained as a subset within Rd can be written as algebraic sum of simple terms, each an integer multiple of the intersection of d or fewer half-spaces defined by facets of P. P can be non-convex and can have holes of any kind. Among the consequences of this result are a short boolean formula for P, a fast parallel algorithm for point classification, and a new proof of the Gram-Sommerville angle relation.
AU - Herbert Edelsbrunner
ID - 4034
TI - Algebraic decomposition of non-convex polyhedra
ER -
TY - JOUR
AB - Let S be a set of n points in ℝd . A set W is a weak ε-net for (convex ranges of)S if, for any T⊆S containing εn points, the convex hull of T intersects W. We show the existence of weak ε-nets of size {Mathematical expression}, where β2=0, β3=1, and βd ≈0.149·2d-1(d-1)!, improving a previous bound of Alon et al. Such a net can be computed effectively. We also consider two special cases: when S is a planar point set in convex position, we prove the existence of a net of size O((1/ε) log1.6(1/ε)). In the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1/ε), which improves a previous bound of Capoyleas.
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
AU - Grigni, Michelangelo
AU - Guibas, Leonidas
AU - Sharir, Micha
AU - Welzl, Emo
ID - 4035
IS - 1
JF - Discrete & Computational Geometry
TI - Improved bounds on weak ε-nets for convex sets
VL - 13
ER -
TY - JOUR
AB - Three replicate lines of Drosophila melanogaster were cultured at each of two temperatures (16.5⚬C and 25⚬C) in population cages for 4 yr. The lifespans of both sexes and the fecundity and fertility of the females were then measured at both experimental temperatures. The characters showed evidence of adaptation; flies of both sexes from each selection regime showed higher longevity, and females showed higher fecundity and fertility, than flies from the other selection regime when they were tested at the experimental temperature at which they had evolved. Calculation of intrinsic rates of increase under different assumptions about the rate of population increase showed that the difference between the lines from the two selection regimes became less the higher the rate of population increase, because the lines were more similar in early adulthood than they were later. Despite the increased adaptation of the low-temperature lines to the low temperature, like the high temperature lines they produced progeny at a higher rate at the higher temperature. The lines may have independently evolved adaptations to their respective thermal regimes during the experiment, or there may have been a trade-off between adaptation to the two temperatures, or mutation pressure may have lowered adaptation to the temperature that the flies no longer encountered.
AU - Partridge, Linda
AU - Barrie, Brian
AU - Nicholas Barton
AU - Fowler, Kevin
AU - French, Vernon
ID - 4296
IS - 3
JF - Evolution; International Journal of Organic Evolution
TI - Rapid laboratory evolution of adult life history traits in Drosophila melanogaster in response to temperature
VL - 49
ER -
TY - JOUR
AB - The F5 (2n = 34) and FM2 (2n = 44-46) chromosome races of the Sceloporus grammicus complex form a parapatric hybrid zone in the Mexican state of Hidalgo, characterized by steep concordant clines among three diagnostic chromosome markers across a straight-line distance of about 2 km. Here, we show that this zone is actually structured into local patches in which hybridization extends over an extremely irregular front. The distribution of hybrid-index (HI) scores across the transect reveals some hybridization at almost all localities mapped in a central 7 km x 3 km area. Pooling the central samples produces both a strong heterozygote deficit for all diagnostic markers and strong linkage disequilibria between all pairwise combinations of these (unlinked) markers. Moreover, a highly significant association exists between the habitat on which each individual was caught and its karyotype (F5 chromosomes are more likely to be found on oak). Analysis of genotype frequencies over a range of spatial scales shows that there is no significant heterozygote deficit or habitat association within local areas of less than about 200 m; however, there is significant linkage disequilibrium over the smallest scales (R = D (pquv)1/2 = 0.29, support limits, 0.18-0.36) over 100 m. These patterns suggest that lizards mate and choose habitats randomly within local patches. This conclusion is supported by mark-recapture estimates of dispersal (≈ 80 m in a generation) and by inference of matings from embryo and maternal karyotypes. Closer examination of the two-dimensional pattern reveals a convoluted cline for all three markers, with a width of 830 m (support limits 770 m-930 m). This cline width, combined with the strength of local linkage disequilibrium, implies a dispersal rate of σ = 160 m in a generation and an effective selection pressure of 30% on each chromosome marker. The proportion of inviable embryos is greater in females from the center of the hybrid zone; this is caused by effects associated with both karyotype and location. The hybrid zone is likely to be maintained by selection against chromosomal heterozygotes, by other kinds of selection against hybrids, and by selection adapting the chromosome races to different habitats. The structure of the contact may be caused by both random drift and by selection in relation to habitat.
AU - Sites, Jack W
AU - Nicholas Barton
AU - Reed, Kent M
ID - 4297
IS - 1
JF - Evolution; International Journal of Organic Evolution
TI - The genetic structure of a mosaic hybrid zone between two chromosome races of the Sceloporus grammicus complex (Sauria, Phrynosomatidae) in central Mexico
VL - 49
ER -
TY - JOUR
AU - Nicholas Barton
ID - 4298
JF - Evolution; International Journal of Organic Evolution
TI - Appendix to "The mixing of genotypes in hybrid zones: a simulation study of multilocus clines", by S J E Baird
VL - 49
ER -
TY - CHAP
AB - This paper is addressed to potential users of HyTech, the Cornell Hybrid Technology Tool, an automatic tool for analyzing hybrid systems. We review the formal technologies that have been incorporated into HyTech, and we illustrate the use of HyTech with three nontrivial case studies.
AU - Thomas Henzinger
AU - Ho, Pei-Hsin
ED - Panos, Antsaklis
ED - Kohn, Wolf
ED - Nerode, Anil
ED - Sastry, Shankar
ID - 4447
T2 - Hybrid Systems II
TI - HyTech: The Cornell Hybrid Technology Tool
VL - 999
ER -
TY - CHAP
AB - We report on several abstract interpretation strategies that are designed to improve the performance of HyTech, a symbolic model checker for linear hybrid systems. We (1) simultaneously compute the target region from different directions, (2) conservatively approximate the target region by dropping constraints, and (3) iteratively refine the approximation until sufficient precision is obtained. We consider the standard abstract convex-hull operator and a novel abstract extrapolation operator.
AU - Thomas Henzinger
AU - Ho, Pei-Hsin
ED - Panos, Antsaklis
ED - Kohn, Wolf
ED - Nerode, Anil
ED - Sastry, Shankar
ID - 4448
T2 - Hybrid Systems II
TI - A note on abstract-interpretation strategies for hybrid automata
VL - 999
ER -
TY - CONF
AB - Hybrid systems model discrete programs that are embedded in continuous environments. Model-checking tools are available for the analysis of linear hybrid systems, whose continuous variables are bounded by piecewise-linear trajectories. Most embedded programs, however, operate in nonlinear environments. We present, analyze, and apply two algorithms for translating nonlinear hybrid systems into linear hybrid systems.
The clock translation replaces nonlinear variables by clock variables; the rate translation approximates nonlinear variables by piecewise-linear envelopes. Both translations are sound for reachability; that is, if we establish a safety property of the translated linear system, we may conclude that the original nonlinear system satisfies the property. The clock translation is also complete for reachability; that is, the original system and the translated system satisfy the same safety properties. The two translations apply to incomparable classes of nonlinear hybrid systems. From the clock translation we obtain a new decidability result for hybrid systems.
With the help of Hytech, a symbolic model checker for linear hybrid systems, we automatically verify a nonlinear railroad gate control program using the clock translation, and a nonlinear temperature control program using the rate translation.
AU - Thomas Henzinger
AU - Ho, Pei-Hsin
ID - 4450
TI - Algorithmic analysis of nonlinear hybrid systems
VL - 939
ER -