A better lower bound for two-circle point labeling

A. Wolff, M. Thon, Y.F. Xu

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    5 Citaties (SciVal)


    Given a set P of n points in the plane, the two-circle point- labeling problem consists of placing 2n uniform, non-intersecting, maximum- size open circles such that each point touches exactly two circles. It is known that it is NP-hard to approximate the label size beyond a factor of ˜ 0.7321. In this paper we improve the best previously known approximation factor from ˜ 0.51 to 2=3. We keep the O(n log n) time and O(n) space bounds of the previous algorithm. As in the previous algorithm we label each point within its Voronoi cell. Unlike that algorithm we explicitely compute the Voronoi diagram, label each point optimally within its cell, compute the smallest label diameter over all points and finally shrink all labels to this size.
    Originele taal-2Engels
    TitelAlgorithms and computation : proceedings 11th international symposium, ISAAC 2000, Taipei, Taiwan, december 18-20, 2000
    RedacteurenD.T. Lee, S.H. Teng
    Plaats van productieBerlin
    ISBN van geprinte versie3-540-41255-7
    StatusGepubliceerd - 2000

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'A better lower bound for two-circle point labeling'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit