TY - JOUR AB - A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear-time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r> 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned. AU - Dobkin, David AU - Edelsbrunner, Herbert AU - Overmars, Mark ID - 4075 IS - 4 JF - Algorithmica SN - 0178-4617 TI - Searching for empty convex polygons VL - 5 ER - TY - CHAP AU - Barton, Nicholas H AU - Clark, A. ED - Wöhrmann, Klaus ED - Jain, Subodh ID - 4311 SN - 978-3642744761 T2 - Population biology: Ecological and evolutionary viewpoints TI - Population structure and processes in evolution ER - TY - JOUR AU - Barton, Nicholas H AU - Jones, Steve ID - 4310 JF - Nature SN - 0028-0836 TI - The language of the genes VL - 346 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 - Henzinger, Thomas A AU - Manna, Zohar AU - Pnueli, Amir ID - 4510 SN - 0-8186-2078-1 T2 - Proceedings of the 5th Jerusalem Conference on Information Technology TI - An interleaving model for real time ER - TY - CONF AB - We introduce a novel extension of propositional modal logic that is interpreted over Kripke structures in which a value is associated with every possible world. These values are. however, not treated as full first-order objects: they can be accessed only by a very restricted form of quantification: the "freeze" quantifier binds a variable to the value of the current world. We present a complete proof system for this ("half-order") modal logic. As a special case, we obtain the real-time temporal logic TPTL of [AH891: the models are restricted to infinite sequences of states, whose values are monotonically increasing natural numbers. The ordering relation between states is interpreted as temporal precedence. while the value associated with a state is interpreted as its "rear time. We extend our proof system to be complete for TPTL. and demonstrate how it can be used to derive real-time properties. AU - Henzinger, Thomas A ID - 4522 SN - 978-0-89791-404-8 T2 - Proceedings of the 9th annual ACM symposium on Principles of distributed computing TI - Half-order modal logic: How to prove real-time properties ER -