We derive tight expressions for the maximum number of k-faces, k=0,...,d-1, of the Minkowski sum, P_1+...+P_r, of r convex d-polytopes P_1,...,P_r in R^d, where d >= 2 and r < d, as a (recursively defined) function on the number of vertices of the polytopes. Our results coincide with those recently proved by Adiprasito and Sanyal [1]. In contrast to Adiprasito and Sanyal's approach, which uses tools from Combinatorial Commutative Algebra, our approach is purely geometric and uses basic notions such as f- and h-vector calculus, stellar subdivisions and shellings, and generalizes the methodology used in [10] and [9] for proving upper bounds on the f-vector of the Minkowski sum of two and three convex polytopes, respectively. The key idea behind our approach is to express the Minkowski sum P_1+...+P_r as a section of the Cayley polytope C of the summands; bounding the k-faces of P_1+...+P_r reduces to bounding the subset of the (k+r-1)-faces of C that contain vertices from each of the r polytopes. We end our paper with a sketch of an explicit construction that establishes the tightness of the upper bounds.

We derive tight expressions for the maximum number of k-faces, 0≤k≤d-1, of the Minkowski sum, P1+P2+P3, of three d-dimensional convex polytopes P1, P2 and P3 in Rd, as a function of the number of vertices of the polytopes, for any d≥2. Expressing the Minkowski sum as a section of the Cayley polytope C of its summands, counting the k-faces of P1+P2+P3 reduces to counting the (k+2)-faces of C which meet the vertex sets of the three polytopes. In two dimensions our expressions reduce to known results, while in three dimensions, the tightness of our bounds follows by exploiting known tight bounds for the number of faces of r d-polytopes in Rd, where r≥d. For d≥4, the maximum values are attained when P1, P2 and P3 are d-polytopes, whose vertex sets are chosen appropriately from three distinct d-dimensional moment-like curves.

We derive tight bounds for the maximum number of k-faces, 0 ≤ k ≤ d − 1, of the Minkowski sum, P1 ⊕ P2, of two d-dimensional convex polytopes P1 and P2, as a function of the number of vertices of the polytopes. For even dimensions d ≥ 2, the maximum values are attained when P1 and P2 are cyclic d-polytopes with disjoint vertex sets. For odd dimensions d ≥ 3, the maximum values are attained when P1 and P2 are ⌊d/2⌋-neighborly d-polytopes, whose vertex sets are chosen appropriately from two distinct d-dimensional moment-like curves.

Given a set Σ of spheres in Ed, with d≥3 and d odd, having a fixed number of m distinct radii ρ1,ρ2,...,ρm, we show that the worst-case combinatorial complexity of the convex hull CHd(Σ) of Σ is Θ(Σ{1≤i≠j≤m}ninj⌊ d/2 ⌋), where ni is the number of spheres in Σ with radius ρi. Our bound refines the worst-case upper and lower bounds on the worst-case combinatorial complexity of CHd(Σ) for all odd d≥3.

In this paper we consider the problem of guarding an art gallery modeled as a polygon, the edges of which are arcs of curves, with edge or mobile guards. Our focus is on piecewise convex polygons, i.e., polygons the edges of which are convex arcs pointing towards the exterior of the polygon. We transform the problem of guarding a piecewise convex polygon to the problem of 2-dominating a properly defined combinatorial triangulation graph with edges or diagonals, where 2-dominance requires that every triangle in the triangulation graph has at least two of its vertices in its 2-dominating set. In this paper we show that: (1) ⌊ n+1 3 ⌋ diagonal guards are always sufficient and sometimes necessary, and (2) ⌊2n+2 5 ⌋ edge guards are always sufficient and ⌊2n 5 ⌋ edge guards are sometimes necessary, in order to 2-dominate a combinatorial triangulation graph. Using these results we then prove that: (1) ⌊ n+1 3 ⌋ mobile guards or ⌊2n+2 5 ⌋ edge guards are always sufficient, (2) ⌊ n 3 ⌋ mobile or edge guards are sometimes necessary, in order to guard a piecewise convex polygon.

We present a methodology for agent modeling that is scalable and efficient. It is based on the integration of nonlinear dynamical systems and kinetic data structures. The method consists of three-layers that model steering, flocking, and crowding agent behaviors among moving and static obstacles in 2 and 3D. The first layer, the local layer is based on the the use of nonlinear dynamical systems theory and models low level behaviors, it is fast and efficient, and does not depend on the total number of agents in the environment. The use of dynamical systems allows the use of continuous numerical parameters with which we can modify the interaction of each agent with the environment. This creates controllable distinctive behaviors. The second layer, a global environment layer consists of a specifically designed kinetic data structure to track efficiently the immediate environment of each agent and know which obstacles/agents are near or visible to the given agent. This layer reduces the complexity in the local layer. In the third layer, a global planning layer, the problem of target tracking is generalized in a way that allows navigation in maze-like terrains, avoidance of local minima and cooperation between agents. We implement this layer based on two approaches that are suitable for different applications. One is to track the closest single moving or static target. The second is to use a pre-specified vector field. This vector can be generated automatically (with harmonic functions, for example) or based on user input to achieve the desired output. We demonstrate the power of the approach through a series of experiments simulating single/multiple agents and crowds moving towards moving/static targets in complex environments.

We propose a speed-up method for discrete-event simulations, including sweep-line or -plane techniques, requiring the repeated calculation of the times at which certain discrete events occur.Instead of calculating these event times precisely, we use interval methods to obtain less expensive approximations that may still be adequate for the simulation.This can happen because some events get descheduled before they actually happen, or because event time comparisons can be resolved using only information about their bounding intervals.The computed intervals are refined as necessary, when greater accuracy is needed.For geometric objects described by polynomials, including moving objects on polynomial trajectories, the proposed method is shown to give a speed-up roughly proportional to the degree of the polynomials.