How to place a point to maximize angles

Boris Aronov, Mark V. Yagnatinsky

    Research output: Contribution to conferencePaper

    Abstract

    We describe a randomized algorithm that, given a set of points in the plane, computes the best location to insert a new point, such that the Delaunay triangulation of the resulting point set has the largest possible minimum angle. The expected running time of our algorithm is at most cubic on any input, improving the roughly quartic time of the best previously known algorithm.

    Original languageEnglish (US)
    Pages259-263
    Number of pages5
    StatePublished - 2013
    Event25th Canadian Conference on Computational Geometry, CCCG 2013 - Waterloo, Canada
    Duration: Aug 8 2013Aug 10 2013

    Other

    Other25th Canadian Conference on Computational Geometry, CCCG 2013
    CountryCanada
    CityWaterloo
    Period8/8/138/10/13

    ASJC Scopus subject areas

    • Geometry and Topology
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'How to place a point to maximize angles'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., & Yagnatinsky, M. V. (2013). How to place a point to maximize angles. 259-263. Paper presented at 25th Canadian Conference on Computational Geometry, CCCG 2013, Waterloo, Canada.