Skip to main content

9 Result(s)

within John Iacono Remove this filter Mathematics Remove this filter

and

  1. No Access

    Article

    Spanning Properties of Theta–Theta-6

    We show that, unlike the Yao–Yao graph \(YY_6\)YY6, the Theta–Theta graph \({\varTheta }{\varTheta }_6\)ΘΘ6 defined by six cones is a spanner for sets of points in convex position. We also show that, for sets of ...

    Mirela Damian, John Iacono, Andrew Winslow in Graphs and Combinatorics (2020)

  2. No Access

    Article

    Subquadratic Algorithms for Algebraic 3SUM

    The 3SUM problem asks if an input n-set of real numbers contains a triple whose sum is zero. We qualify such a triple of degenerate because the probability of finding one in a random input is zero. We consider th...

    Luis Barba, Jean Cardinal, John Iacono… in Discrete & Computational Geometry (2019)

  3. No Access

    Article

    Incremental Voronoi Diagrams

    We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the graph structure of the Voronoi diagram (and several variants thereof) of a set S of n sites in the plane ...

    Sarah R. Allen, Luis Barba, John Iacono… in Discrete & Computational Geometry (2017)

  4. No Access

    Article

    Coverage with k-transmitters in the presence of obstacles

    For a fixed integer k≥0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k “walls”, represented as line segments in the plane. We develo...

    Brad Ballinger, Nadia Benbernou, Prosenjit Bose… in Journal of Combinatorial Optimization (2013)

  5. No Access

    Article

    Continuous Blooming of Convex Polyhedra

    We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a ...

    Erik D. Demaine, Martin L. Demaine, Vi Hart, John Iacono… in Graphs and Combinatorics (2011)

  6. Article

    Geodesic Ham-Sandwich Cuts

    Let P be a simple polygon with m vertices, k of which are reflex, and which contains r red points and b blue points in its interior. Let n = m + r + b. A ham-sandwich geodesic is a shortest path in P between t...

    Prosenjit Bose, Erik D. Demaine, Ferran Hurtado… in Discrete & Computational Geometry (2007)

    Download PDF (241 KB)

  7. Article

    Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries

    Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ⋃ B comes from R (respectively, B...

    David Bremner, Erik Demaine, Jeff Erickson… in Discrete & Computational Geometry (2005)

    Download PDF (194 KB)

  8. No Access

    Chapter and Conference Paper

    Queaps

    We present a new priority queue data structure, the queap, that executes insertion in O(1) amortized time and Extract-min in O(log(k + 2)) amortized time if there are k items that have been in the heap longer tha...

    John Iacono, Stefan Langerman2 in Algorithms and Computation (2002)

  9. No Access

    Chapter and Conference Paper

    Key Independent Optimality

    A new form of optimality for comparison based static dictionaries is introduced. This type of optimality, key-independent optimality, is motivated by applications that assign key values randomly. It is shown t...

    John Iacono in Algorithms and Computation (2002)