TY - JOUR AB - We prove that given n⩾3 convex, compact, and pairwise disjoint sets in the plane, they may be covered with n non-overlapping convex polygons with a total of not more than 6n−9 sides, and with not more than 3n−6 distinct slopes. Furthermore, we construct sets that require 6n−9 sides and 3n−6 slopes for n⩾3. The upper bound on the number of slopes implies a new bound on a recently studied transversal problem. AU - Edelsbrunner, Herbert AU - Robison, Arch AU - Shen, Xiao ID - 4065 IS - 2 JF - Discrete Mathematics SN - 0012-365X TI - Covering convex sets with non-overlapping polygons VL - 81 ER - TY - JOUR AB - We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n), and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m 4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given. AU - Clarkson, Kenneth AU - Edelsbrunner, Herbert AU - Guibas, Leonidas AU - Sharir, Micha AU - Welzl, Emo ID - 4074 IS - 1 JF - Discrete & Computational Geometry SN - 0179-5376 TI - Combinatorial complexity bounds for arrangements of curves and spheres VL - 5 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 - Edelsbrunner, Herbert AU - Guibas, Leonidas AU - Hershberger, John AU - Seidel, Raimund AU - Sharir, Micha ID - 4078 SN - 978-0-89791-362-1 T2 - Proceedings of the 6th annual symposium on computational geometry TI - Slimming down by adding; selecting heavily covered points ER - TY - CONF AB - We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in Ed in time O(Td(N, N) logd N), where Td(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in Ed. If Td(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves to O(Td(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closets pair in expected time O((nm log n log m)2/3+m log2 n + n log2 m) in E3, which yields an O(N4/3log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in E3. AU - Agarwal, Pankaj AU - Edelsbrunner, Herbert AU - Schwarzkopf, Otfried AU - Welzl, Emo ID - 4076 SN - 978-0-89791-362-1 T2 - Proceedings of the 6th annual symposium on Computational geometry TI - Euclidean minimum spanning trees and bichromatic closest pairs ER - 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 - Edelsbrunner, Herbert AU - Guibas, Leonidas AU - Sharir, Micha AU - Wenger, Rephael ID - 4077 SN - 978-0-89791-362-1 T2 - Proceedings of the 6th annual symposium on Computational geometry TI - Points and triangles in the plane and halving planes in space ER - 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 - TY - CONF AB - A unifying framework for the study of real-time logics is developed. In analogy to the untimed case, the underlying classical theory of timed state sequences is identified, it is shown to be nonelementarily decidable, and its complexity and expressiveness are used as a point of reference. Two orthogonal extensions of PTL (timed propositional temporal logic and metric temporal logic) that inherit its appeal are defined: they capture elementary, yet expressively complete, fragments of the theory of timed state sequences, and thus are excellent candidates for practical real-time specification languages AU - Alur, Rajeev AU - Henzinger, Thomas A ID - 4597 SN - 0-8186-2073-0 T2 - 5th Annual IEEE Symposium on Logic in Computer Science TI - Real-time logics: Complexity and expressiveness ER -