A sweepline algorithm to solve the two-center problem

DOI10.1016/0020-0190(94)90007-8MaRDI QIDQ1318733zbMATH OpenOpenAlexFDO

Authors Nen-Fu Huang, Ching-Ho Huang, Yue-Li Wang

Publication date 5 April 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)90007-8

zbMATH Keywords

average-case performancecomputational geometrygeometric location problemsweepline algorithmtwo-center problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Given a set \(N= \{p_ 1,p_ 2,\dots,p_ n\}\) of \(n\) points in the plane, the two-center problem is to allocate two circles such that all the points in \(N\) are covered by the two circles (each point is covered by at least one circle) and the radius of the bigger circle is minimized. In this paper, a sweepline algorithm has been proposed to solve the two- center problem with time complexity \(O(n^ 2\log n+ H(N))\); where \(H(N)\) is a function of the given point set \(N\) and \(H(N)\leq n^ 3\). The average case time complexity of the proposed algorithm is also analyzed. If the given \(n\) points are uniformly dispersed in a convex polygon, then we show that the proposed two-center algorithm has an expected time complexity \(O(n^ 2\log n)\).

Recommendations

• More planar two-center algorithms
• The discrete 2-center problem
• A faster algorithm for the two-center decision problem
• Efficient planar two-center algorithms
• A near-linear algorithm for the planar 2-center problem

Cites work

• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• scientific article; zbMATH DE number 432848 (Why is no real title available?)
• scientific article; zbMATH DE number 3172297 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• On the Average Number of Maxima in a Set of Vectors and Applications
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten

Cited in

(2)

• A fast algorithm for the alpha-connected two-center decision problem
• The two-line center problem from a polar view: a new algorithm and data structure

This page was built for publication: A sweepline algorithm to solve the two-center problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1318733)