arxiv: 2604.10828 · v1 · submitted 2026-04-12 · 💻 cs.CG · cs.DS

Recognition: no theorem link

Maximum Independent Sets in Disk Graphs with Disks in Convex Position

Anastasiia Tkachenko , Haitao Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:45 UTC · model grok-4.3

classification 💻 cs.CG cs.DS

keywords disk graphsmaximum independent setconvex positiondynamic programmingdispersion problemweighted independent setcomputational geometry

0 comments

The pith

When all disks lie on the convex hull, an O(n^3 log n)-time algorithm solves the maximum weighted independent set problem in their intersection graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a polynomial-time algorithm for the maximum (weighted) independent set in a disk intersection graph when every disk touches the outer convex hull. This geometric restriction supplies a natural cyclic ordering that supports an efficient recurrence, turning an NP-hard problem into one that runs in O(n^3 log n) time. The same method produces an O(n^3 log^2 n) algorithm for the dispersion task of selecting k disks that maximize the minimum pairwise distance.

Core claim

For any set of n disks whose boundaries all appear on the convex hull of the union, there exists an O(n^3 log n)-time algorithm that returns a maximum-weight subset of pairwise non-intersecting disks. The algorithm also solves the unweighted case and improves the prior O(n^{37/11}) bound known for equal-radius disks.

What carries the argument

The cyclic ordering of the disks around the convex hull, which permits a dynamic-programming recurrence that considers intervals of consecutive disks on the boundary.

Load-bearing premise

The disks must all touch the convex hull so that they possess a well-defined cyclic order without interior disks.

What would settle it

A concrete set of n disks in convex position together with a larger-weight independent set than the one returned by the algorithm.

Figures

Figures reproduced from arXiv: 2604.10828 by Anastasiia Tkachenko, Haitao Wang.

**Figure 1.** Figure 1: Illustrating a set of disks in convex position. The red dashed segments are on the boundary of the convex hull of all disks [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 3.** Figure 3: Illustrating the proof of Lemma 5. This completes the proof of the lemma. 3.2 Algorithm correctness: Proving Lemma 3 We now prove Lemma 3. Consider a canonical triple (i, j, k). Without loss of generality, we assume that the centers pi and pj of disks Di and Dj lie on the same horizontal line, with pi to the left of pj . This assumption allows us to clearly distinguish the upper and lower (outer) common ta… view at source ↗

**Figure 4.** Figure 4: Illustrating Lemma 6. The three dashed curves (two red and one blue) are edges of Voronoi diagram of the three disks. The blue curve belongs to γij . contains a disk Dl ∈ D′ k (i, j) such that S can be partitioned as S = S1 ∪S2 ∪ {Dl}, where S1 ⊆ Dj (i, l) and S2 ⊆ Di(l, j), and both S1 ∪ {Di , Dl} and S2 ∪ {Dl , Dj} are strongly convex independent sets. This implies that f(i, j, k) ≤ maxDl∈D′ k (i,j) [PI… view at source ↗

**Figure 5.** Figure 5: The disk Dh can only be in one of the two shaded regions. The curve γij is the bisector of Di and Dj , and γih is the bisector of Di and Dh. The two bisectors are the only two edges of the Voronoi diagram of the three disks. Dl is unique. Define S1 = S ∩ D(i, l) and S2 = S ∩ D(l, j). Since S ⊆ Dk(i, j), the sets S1, S2, and {Dl} form a partition of S. By definition, Dl ∈ D′ k (i, j). To complete the proof … view at source ↗

**Figure 6.** Figure 6: Illustrating the proof of Lemma 8. The blue disk arcs are on ∂R1. The red disk arcs are on ∂R2. Consider the region R1 bounded by following curves in the counterclockwise order (see [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗

**Figure 7.** Figure 7: Illustrating the proof of Lemma 10. The blue curve is ∂[qi,ql ]H(S ′ 1) and the red curve is ∂[ql ,qi]H(D ′ ). ∂H(D ′ 1) is exactly the union of the two curves. We consider Voronoi diagram Vor(D′ 1 ) of the disks of D′ 1 . Since S1 ⊆ Dj (i, l), no disk of S1 intersects the disk Dijl. This implies that the center vijl of Dijl is a Voronoi vertex of Vor(D′ 1 ) since it is equidistant from Di , Dl , and Dj . … view at source ↗

**Figure 8.** Figure 8: Illustrating the proof of Lemma 11. R1 is bounded by the green curve and the three blue disk arcs, and R2 is bounded by the orange curve and the three red disk arcs. All disks of S1 (resp., S2) are in R1 (resp., R2). Due to the convexity of the three arcs αi , αl , and αj , ∂H(S ′ ) is exactly ∂[qi,ql ]H(S ′ 1 )∪∂[ql ,qj ]H(S ′ 2 )∪ ∂[qj ,qi]H({Di , Dj}); see [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗

**Figure 9.** Figure 9: Illustrating an example where the input set of disks is strongly convex, but the only maximum-weight independent set (shown in red) is not strongly convex (assuming the weight of each disk is 1). 4 The strongly-convex-input case In this section, we consider the strongly-convex-input case, in which the input disks of D are in strongly convex position but D does not necessarily admit a maximum-weight indepen… view at source ↗

**Figure 10.** Figure 10: Illustrating the definition of bi. convex hull H(D) lies entirely to the left of ρi,i+1, and the segment of ρi,i+1 between the two tangency points on Di and Di+1 forms an edge of H(D). Since ℓi is tangent to Di at the midpoint of αi , the line ℓi must intersect ρi,i+1. Similarly, ℓi+1 intersects ρi,i+1. Moreover, because n ≥ 3, the lines ℓi and ℓi+1 intersect at a point bi that lies to the right of ρi,i+1… view at source ↗

**Figure 11.** Figure 11: Illustrating the definition of Q (the gray region). Di other than ai are in the interior of Hi . Consequently, all points of Di except ai are in the interior of Q. Therefore, ai is in the only point of Di appearing on ∂Q. With the above discussions, we are now in a position to prove the second property of B. Consider a subset D′ ⊆ D. Our goal is to show that S ′ = D′ ∪ B is strongly convex. To this end, w… view at source ↗

**Figure 12.** Figure 12: Illustration of the definition of z. In the rest of this section, we will focus on defining a set Z of O(n) points satisfying the above two properties. We will also show that computing Z can be done in O(n log n) time. Consider a disk Di that has more than one arc on ∂H(D). Note that at most one such arc can have a radian measure larger than or equal to π, and all other arcs have median measures strictly … view at source ↗

read the original abstract

For a set $\mathcal{D}$ of disks in the plane, its disk graph $G(\mathcal{D})$ is the graph with vertex set $\mathcal{D}$, where two vertices are adjacent if and only if the corresponding disks intersect. Given a set $\mathcal{D}$ of $n$ weighted disks, computing a maximum independent set of $G(\mathcal{D})$ is NP-hard. In this paper, we present an $O(n^3\log n)$-time algorithm for this problem in a special setting in which the disks are in convex position, meaning that every disk appears on the convex hull of $\mathcal{D}$. This setting has been studied previously for disks of equal radius, for which an $O(n^{37/11})$-time algorithm was known. Our algorithm also works in the weighted case where disks have weights and the goal is to compute a maximum-weight independent set. As an application of our result, we obtain an $O(n^3\log^2 n)$-time algorithm for the dispersion problem on a set of $n$ disks in convex position: given an integer $k$, compute a subset of $k$ disks that maximizes the minimum pairwise distance among all disks in the subset.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean O(n^3 log n) algorithm for weighted max independent set on disk graphs with all disks on the convex hull, extending the equal-radius case and adding a dispersion application.

read the letter

The main takeaway is an O(n^3 log n) algorithm for maximum-weight independent set in disk intersection graphs when every disk touches the convex hull of the set. This is new for the weighted and varying-radius version, and it improves the earlier O(n^{37/11}) bound that was limited to equal radii. The dispersion follow-up, which finds k disks maximizing the minimum pairwise distance in O(n^3 log^2 n) time, is a direct and practical consequence. The convex-position restriction supplies a cyclic order that supports dynamic programming over contiguous arcs, with states that track a small number of boundary disks and a logarithmic factor from priority queues or binary search inside the transitions. That structure explains why the runtime stays polynomial while the general problem stays NP-hard. The paper does well by keeping the extension to weights and radii straightforward without extra assumptions or hidden parameters. The abstract states the result plainly and cites the prior equal-radius work, so the novelty is easy to locate. No circular reasoning or fitted quantities appear. The central claim holds up on its own terms: the ordering gives a natural recurrence, and nothing in the high-level description suggests missing base cases or unjustified steps. A minor soft spot is that the cubic dependence might still have room for improvement with better data structures, but that is normal for a first polynomial bound and not a flaw in the current argument. This is for computational geometers and algorithm researchers who work on intersection graphs or geometric dispersion. A reader who needs exact solutions on restricted disk inputs will get concrete value from the technique and the application. It deserves a serious referee because the result is explicit, the setting is natural, and the improvement over prior work is clear.

Referee Report

0 major / 3 minor

Summary. The paper presents an O(n^3 log n)-time algorithm for computing a maximum-weight independent set in the intersection graph of n disks whose boundaries all touch the convex hull of their union (i.e., disks in convex position). This improves on the prior O(n^{37/11}) bound known for the equal-radius special case. The same approach yields an O(n^3 log^2 n)-time algorithm for the k-dispersion problem on such disks.

Significance. If correct, the result is significant because it supplies a polynomial-time algorithm for a geometrically restricted but still NP-hard problem by exploiting the cyclic ordering induced by convex position. The extension to the weighted setting and the concrete application to dispersion are useful additions. The runtime improvement over the equal-radius literature is substantial and the DP-based approach appears to be a natural fit for the cyclic structure.

minor comments (3)

[3] §3 (Algorithm): the recurrence and state definition are clear, but the precise origin of the log n factor in the transition time (priority queue or binary search over candidate boundary disks) would benefit from an explicit sentence or small example.
[2] Figure 2: the illustration of the cyclic ordering and the 'active arc' maintained by the DP would be easier to follow if the disks were labeled with their indices in the hull order.
[4] Theorem 1: the statement of the running time is correct, but the proof sketch in the text could explicitly cite the O(n) subproblems per layer and the O(n^2 log n) work per layer to make the cubic bound immediate.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of our paper, as well as the recommendation for minor revision. The referee's description of the O(n^3 log n) algorithm for maximum-weight independent set and the O(n^3 log^2 n) result for k-dispersion on disks in convex position accurately reflects the manuscript.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents a direct algorithmic construction of an O(n^3 log n)-time dynamic programming procedure that exploits the cyclic ordering induced by convex position of the disks. No equations, fitted parameters, or predictions appear; the runtime and correctness claims follow from the recurrence structure on contiguous arcs rather than any reduction to prior fitted quantities or self-citations. The improvement over the equal-radius bound is presented as a consequence of the added convex-position structure, not as a renaming or self-referential derivation. The result is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that the input disks satisfy convex position, which enables an ordering-based algorithm whose internal steps are not visible in the abstract.

axioms (1)

domain assumption Disks are in convex position (every disk lies on the convex hull of the set)
Stated explicitly in the abstract as the special setting that makes the polynomial-time algorithm possible.

pith-pipeline@v0.9.0 · 5513 in / 1255 out tokens · 28839 ms · 2026-05-10T15:45:17.351270+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

34 extracted references · 27 canonical work pages

[1]

Agarwal and Nabil H

Pankaj K. Agarwal and Nabil H. Mustafa. Independent set of intersection graphs of convex objects in 2D.Computational Geometry: Theory and Applications, 34(2):83–95, 2006.doi: 10.1016/j.comgeo.2005.12.001. 1, 2

work page doi:10.1016/j.comgeo.2005.12.001 2006
[2]

Agarwal, Mark H

Pankaj K. Agarwal, Mark H. Overmars, and Micha Sharir. Computing maximally separated sets in the plane.SIAM Journal on Computing, 36(3):815–834, 2006.doi:10.1137/S0097539704446591. 3

work page doi:10.1137/s0097539704446591 2006
[3]

Agarwal, Marc J

Pankaj K. Agarwal, Marc J. van Kreveld, and Subhash Suri. Label placement by maximum independent set in rectangles.Computational Geometry: Theory and Applications, 11:209–218, 1998.doi:10.1016/S0925-7721(98)00028-5. 2

work page doi:10.1016/s0925-7721(98)00028-5 1998
[4]

Guibas, James Saxe, and Peter W

Alok Aggarwal, Leonidas J. Guibas, James Saxe, and Peter W. Shor. A linear-time algorithm for computing the Voronoi diagram of a convex polygon.Discrete and Computational Geometry, 4:591–604, 1989.doi:10.1007/BF02187749. 3

work page doi:10.1007/bf02187749 1989
[5]

Atallah, and Susanne E

Alberto Apostolico, Mikhail J. Atallah, and Susanne E. Hambrusch. New clique and independent set algorithms for circle graphs.Discrete Applied Mathematics, 36(1):1–24, 1992.doi:10.1016/ 0166-218X(92)90200-T. 1, 2

1992
[6]

Connectivity of random k- nearest-neighbour graphs.Advances in Applied Probability, 37(1):1–24, 2005.doi:doi:10.1239/ aap/1113402397

Paul Balister, Béla Bollobás, Amites Sarkar, and Mark Walters. Connectivity of random k- nearest-neighbour graphs.Advances in Applied Probability, 37(1):1–24, 2005.doi:doi:10.1239/ aap/1113402397. 1

work page arXiv 2005
[7]

Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, Ren´ e Sitters, and Thomas Wolle

Prosenjit Bose, Paz Carmi, J Mark Keil, Anil Maheshwari, Saeed Mehrabi, Debajyoti Mondal, and Michiel Smid. Computing maximum independent set on outerstring graphs and their relatives. Computational Geometry: Theory and Applications, 103:101852, 2022.doi:10.1016/j.comgeo. 2021.101852. 1 20

work page doi:10.1016/j.comgeo 2022
[8]

Maximum clique of disks in convex position

Onur Çağı rıcıand Bodhayan Roy. Maximum clique of disks in convex position. InAbstracts of Computational Geometry: Young Researchers Forum (CG:YRF), pages 21:1–21:3, 2018. URL: https://www.computational-geometry.org/old/YRF/cgyrf2018.pdf. 3

2018
[9]

Timothy M. Chan. Approximation algorithms for maximum independent set of pseudo-disks. Discrete and Computational Geometry, 48:373–392, 2012.doi:10.1007/s00454-012-9417-5. 2

work page doi:10.1007/s00454-012-9417-5 2012
[10]

Improved bounds on weakϵ-nets for convex sets

Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl. Improved bounds on weakϵ-nets for convex sets. InProceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 495–504, 1993.doi:10.1145/ 167088.167222. 3

work page arXiv 1993
[11]

Efficientk-center algorithms for planar points in convex position

Jongmin Choi, Jaegun Lee, and Hee-Kap Ahn. Efficientk-center algorithms for planar points in convex position. InProceedings of the 18th Algorithms and Data Structures Symposium (WADS), pages 262–274, 2023.doi:10.1007/978-3-031-38906-1_18. 3

work page doi:10.1007/978-3-031-38906-1_18 2023
[12]

Clark, Charles J

Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs.Discrete Mathe- matics, 86:165–177, 1990.doi:10.1016/0012-365X(90)90358-O. 1, 2

work page doi:10.1016/0012-365x(90)90358-o 1990
[13]

Das, Guilherme D

Gautam K. Das, Guilherme D. da Fonseca, and Ramesh K. Jallu. Efficient independent set approximation in unit disk graphs.Discrete Applied Mathematics, 280:63–70, 2020.doi:10. 1016/j.dam.2018.05.049. 2

2020
[14]

Das, Minati De, Sudeshna Kolay, Subhas C

Gautam K. Das, Minati De, Sudeshna Kolay, Subhas C. Nandy, and Susmita Sur-Kolay. Approx- imation algorithms for maximum independent set of a unit disk graph.Information Processing Letters, 115:439–446, 2015.doi:10.1016/j.ipl.2014.11.002. 2

work page doi:10.1016/j.ipl.2014.11.002 2015
[15]

Trapezoid graphs and generalizations, geometry and algorithms.Discrete Applied Mathematics, 74(1):13–32, 1997.doi:10.1016/ S0166-218X(96)00013-3

Stefan Felsner, Rudolf Müller, and Lorenz Wernisch. Trapezoid graphs and generalizations, geometry and algorithms.Discrete Applied Mathematics, 74(1):13–32, 1997.doi:10.1016/ S0166-218X(96)00013-3. 1

1997
[16]

Fănică Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph.SIAM Journal on Computing, 1(2):180–187, 1972.doi:10.1137/0201013. 1

work page doi:10.1137/0201013 1972
[17]

Algorithms for a maximum clique and a maximum independent set of a circle graph.Networks, 3(3):261–273, 1973.doi:10.1002/net.3230030305

Fănică Gavril. Algorithms for a maximum clique and a maximum independent set of a circle graph.Networks, 3(3):261–273, 1973.doi:10.1002/net.3230030305. 1

work page doi:10.1002/net.3230030305 1973
[18]

Herrera and Pablo Pérez-Lantero

Luis H. Herrera and Pablo Pérez-Lantero. On the intersection graph of the disks with diameters the sides of a convexn-gon.Applied Mathematics and Computation, 411:126472, 2021.doi: 10.1016/j.amc.2021.126472. 3

work page doi:10.1016/j.amc.2021.126472 2021
[19]

Almost color-balanced perfect matchings in color-balanced complete graphs

Clemens Huemer and Pablo Pérez-Lantero. The intersection graph of the disks with diameters the sides of a convex n-gon.Discrete Mathematics, 343(2):111669, 2020.doi:10.1016/j.disc. 2019.111669. 3

work page doi:10.1016/j.disc 2020
[20]

Richard M. Karp. Reducibility among combinatorial problems.Complexity of Computer Compu- tations, pages 85–103, 1972.doi:10.1007/978-1-4684-2001-2_9. 1

work page doi:10.1007/978-1-4684-2001-2_9 1972
[21]

On approximation behavior and implementation of the greedy triangulation for convex planar point sets

Andrzej Lingas. On approximation behavior and implementation of the greedy triangulation for convex planar point sets. InProceedings of the 2nd Annual Symposium on Computational Geometry (SoCG), pages 72–79, 1986.doi:10.1145/10515.10523. 3 21

work page doi:10.1145/10515.10523 1986
[22]

Marathe, Heinz Breu, Harry B

Madhav V. Marathe, Heinz Breu, Harry B. Hunt III, Sekharipuram S. Ravi, and Daniel J. Rosenkrantz. Simple heuristics for unit disk graphs.Networks, 25:59–68, 1995.doi:10.1002/ net.3230250205. 2

1995
[23]

Approximation algorithms for maximum independent set problems and frac- tional coloring problems on unit disk graphs

Tomomi Matsui. Approximation algorithms for maximum independent set problems and frac- tional coloring problems on unit disk graphs. InProceedings of the 2nd Japanese Confer- ence on Discrete and Computational Geometry (JCDCG), pages 194–200, 1998.doi:10.1007/ 978-3-540-46515-7_16. 2

1998
[24]

Perkins and Pravin Bhagwat

Charles E. Perkins and Pravin Bhagwat. Highly dynamic destination-sequenced distance-vector routing (dsdv) for mobile computers. InProceedings of the Conference on Communications Archi- tectures, Protocols and Applications (SIGCOMM), pages 234–244, 1994.doi:10.1145/190809. 190336. 1

work page doi:10.1145/190809 1994
[25]

Ad-hocon-demanddistancevectorrouting

CharlesE.PerkinsandPravinBhagwat. Ad-hocon-demanddistancevectorrouting. InProceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), pages 90– 100, 1999.doi:10.1109/MCSA.1999.749281. 1

work page doi:10.1109/mcsa.1999.749281 1999
[26]

A convex hull algorithm for discs, and applications.Computational Geometry: Theory and Applications, 1(3):171–187, 1992.doi:10.1016/0925-7721(92)90015-K

David Rappaport. A convex hull algorithm for discs, and applications.Computational Geometry: Theory and Applications, 1(3):171–187, 1992.doi:10.1016/0925-7721(92)90015-K. 16, 19

work page doi:10.1016/0925-7721(92)90015-k 1992
[27]

Richards and Jeffrey S

Dana S. Richards and Jeffrey S. Salowe. A rectilinear steiner minimal tree algorithm for convex point sets. InProceedings of the 2nd Scandinavian Workshop on Algorithm Theory (SWAT), pages 201–212, 1990.doi:10.1007/3-540-52846-6_90. 3

work page doi:10.1007/3-540-52846-6_90 1990
[28]

Polynomial-time recognition and maximum independent set in burling graphs

Paweł Rzążewski and Bartosz Walczak. Polynomial-time recognition and maximum independent set in burling graphs. InProceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 445–460, 2026.doi:10.1007/978-3-032-11835-6_32. 1

work page doi:10.1007/978-3-032-11835-6_32 2026
[29]

Intersection and closest-pair problems for a set of planar discs.SIAM Journal on Computing, 14(2):448–468, 1985.doi:10.1137/0214034

Micha Sharir. Intersection and closest-pair problems for a set of planar discs.SIAM Journal on Computing, 14(2):448–468, 1985.doi:10.1137/0214034. 4, 5, 8, 10, 12

work page doi:10.1137/0214034 1985
[30]

Singireddy, Manjanna Basappa, and Joseph S.B

Vishwanath R. Singireddy, Manjanna Basappa, and Joseph S.B. Mitchell. Algorithms fork- dispersion for points in convex position in the plane. InProceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), pages 59–70, 2023. doi:10.1007/978-3-031-25211-2_5. 2, 3

work page doi:10.1007/978-3-031-25211-2_5 2023
[31]

Computing dominating sets in disk graphs with centers in convex position

Anastasiia Tkachenko and Haitao Wang. Computing dominating sets in disk graphs with centers in convex position. InProceedings of the 17th Latin American Theoretical Informatics Symposium (LATIN), page to appear, 2025.doi:10.48550/arXiv.2601.22609. 3

work page doi:10.48550/arxiv.2601.22609 2025
[32]

Computing maximum cliques in unit disk graphs

Anastasiia Tkachenko and Haitao Wang. Computing maximum cliques in unit disk graphs. In Proceedings of the 37th Canadian Conference on Computational Geometry (CCCG), pages 283– 291, 2025. URL:https://cccg-wads-2025.eecs.yorku.ca/cccg-papers/6B2.pdf. 3

2025
[33]

Dominating set, independent set, discretek-center, dispersion, and related problems for planar points in convex position

Anastasiia Tkachenko and Haitao Wang. Dominating set, independent set, discretek-center, dispersion, and related problems for planar points in convex position. InProceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science (STACS), pages 73:1–73:20, 2025.doi:10.4230/LIPIcs.STACS.2025.73. 2, 3

work page doi:10.4230/lipics.stacs.2025.73 2025
[34]

A study on two geometric location problems.Information processing letters, 28(6):281–286, 1988.doi:10.1016/0020-0190(88)90174-3

Da-Wei Wang and Yue-Sun Kuo. A study on two geometric location problems.Information processing letters, 28(6):281–286, 1988.doi:10.1016/0020-0190(88)90174-3. 3 22

work page doi:10.1016/0020-0190(88)90174-3 1988