TY - CONF
AB - We prove that for any set S of n points in the plane and n3-α triangles spanned by the points of S there exists a point (not necessarily of S) contained in at least n3-3α/(512 log25 n) of the triangles. This implies that any set of n points in three - dimensional space defines at most 6.4n8/3 log5/3 n halving planes.
AU - Aronov, Boris
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas J
AU - Sharir, Micha
AU - Wenger, Rephael
ID - 4077
TI - Points and triangles in the plane and halving planes in space
ER -
TY - CONF
AB - In this paper we derived combinatorial point selection results for geometric objects defined by pairs of points. In a nutshell, the results say that if many pairs of a set of n points in some fixed dimension each define a geometric object of some type, then there is a point covered by many of these objects. Based on such a result for three-dimensional spheres we show that the combinatorial size of the Delaunay triangulation of a point set in space can be reduced by adding new points. We believe that from a practical point of view this is the most important result of this paper.
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas J
AU - Hershberger, John E
AU - Seidel, Raimund
AU - Sharir, Micha
ID - 4078
TI - Slimming down by adding; selecting heavily covered points
ER -
TY - GEN
AU - Nicholas Barton
AU - Jones, Steve
ID - 4310
T2 - Nature
TI - The language of the genes
VL - 346
ER -
TY - CHAP
AU - Nicholas Barton
AU - Clark,A.
ED - Wöhrmann, Klaus
ED - Jain, Subodh K
ID - 4311
T2 - Population biology: ecological and evolutionary viewpoints
TI - Population structure
ER -
TY - CONF
AB - The interleaving model is both adequate and sufficiently abstract to allow for the practical specification and verification of many properties of concurrent systems. We incorporate real time into this model by defining the abstract notion of a real-time transition system as a conservative extension of traditional transition systems: qualitative fairness requirements are replaced (and superseded) by quantitative lower-bound and upper-bound real-time requirements for transitions.
We present proof rules to establish lower and upper real-time bounds for response properties of real-time transition systems. This proof system can be used to verify bounded-invariance and bounded-response properties, such as timely termination of shared-variables multi-process systems, whose semantics is defined in terms of real-time transition systems.
AU - Thomas Henzinger
AU - Manna, Zohar
AU - Pnueli,Amir
ID - 4510
TI - An interleaving model for real time
ER -