@article{4028,
abstract = {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.},
author = {Herbert Edelsbrunner},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {415 -- 440},
publisher = {Springer},
title = {{The union of balls and its dual shape}},
doi = {10.1007/BF02574053},
volume = {13},
year = {1995},
}
@article{4029,
abstract = {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.},
author = {Delfinado, Cecil J and Herbert Edelsbrunner},
journal = {Computer Aided Geometric Design},
number = {7},
pages = {771 -- 784},
publisher = {Elsevier},
title = {{An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere}},
doi = {10.1016/0167-8396(95)00016-Y},
volume = {12},
year = {1995},
}
@inproceedings{4034,
abstract = {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.},
author = {Herbert Edelsbrunner},
pages = {248 -- 257},
publisher = {IEEE},
title = {{Algebraic decomposition of non-convex polyhedra}},
year = {1995},
}
@article{4035,
abstract = {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.},
author = {Chazelle, Bernard and Herbert Edelsbrunner and Grigni, Michelangelo and Guibas, Leonidas and Sharir, Micha and Welzl, Emo},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {1 -- 15},
publisher = {Springer},
title = {{Improved bounds on weak ε-nets for convex sets}},
doi = {10.1007/BF02574025},
volume = {13},
year = {1995},
}
@article{4296,
abstract = {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.},
author = {Partridge, Linda and Barrie, Brian and Nicholas Barton and Fowler, Kevin and French, Vernon},
journal = {Evolution; International Journal of Organic Evolution},
number = {3},
pages = {538 -- 544},
publisher = {Wiley-Blackwell},
title = {{Rapid laboratory evolution of adult life history traits in Drosophila melanogaster in response to temperature}},
volume = {49},
year = {1995},
}
@article{4297,
abstract = {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.},
author = {Sites, Jack W and Nicholas Barton and Reed, Kent M},
journal = {Evolution; International Journal of Organic Evolution},
number = {1},
pages = {9 -- 36},
publisher = {Wiley-Blackwell},
title = {{The genetic structure of a mosaic hybrid zone between two chromosome races of the Sceloporus grammicus complex (Sauria, Phrynosomatidae) in central Mexico}},
volume = {49},
year = {1995},
}
@article{4298,
author = {Nicholas Barton},
journal = {Evolution; International Journal of Organic Evolution},
pages = {1038 -- 1045},
publisher = {Wiley-Blackwell},
title = {{Appendix to "The mixing of genotypes in hybrid zones: a simulation study of multilocus clines", by S J E Baird}},
volume = {49},
year = {1995},
}
@inbook{4447,
abstract = {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.},
author = {Thomas Henzinger and Ho, Pei-Hsin},
booktitle = {Hybrid Systems II},
editor = {Panos, Antsaklis and Kohn, Wolf and Nerode, Anil and Sastry, Shankar},
pages = {265 -- 293},
publisher = {Springer},
title = {{HyTech: The Cornell Hybrid Technology Tool}},
doi = {10.1007/3-540-60472-3_14},
volume = {999},
year = {1995},
}
@inbook{4448,
abstract = {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.},
author = {Thomas Henzinger and Ho, Pei-Hsin},
booktitle = {Hybrid Systems II},
editor = {Panos, Antsaklis and Kohn, Wolf and Nerode, Anil and Sastry, Shankar},
pages = {252 -- 264},
publisher = {Springer},
title = {{A note on abstract-interpretation strategies for hybrid automata}},
doi = {10.1007/3-540-60472-3_13},
volume = {999},
year = {1995},
}
@inproceedings{4450,
abstract = {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.},
author = {Thomas Henzinger and Ho, Pei-Hsin},
pages = {225 -- 238},
publisher = {Springer},
title = {{Algorithmic analysis of nonlinear hybrid systems}},
doi = {10.1007/3-540-60045-0_53},
volume = {939},
year = {1995},
}