Scholarlink

<p>We study a geometric facility location problem under imprecision. Given <i>n</i> unit segments on the real line, each with one of <i>k</i> colors, the goal is to place a point on each segment such that the resulting <i>minimum color-spanning interval</i> is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given segment of each color. We prove that if the input segments are pairwise disjoint, the problem can be solved in <i>O</i>(<i>n</i>) time, even for segments of arbitrary length. For overlapping segments, the problem becomes much more difficult. Nevertheless, we show that it can be solved in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(n \log ^2 n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <msup> <mo>log</mo> <mn>2</mn> </msup> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time when <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(k=2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Computing Largest Minimum Color-Spanning Intervals of Imprecise Points

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年4月30日

查看全文
  • Ankush Acharyya,
  • Vahideh Keikha,
  • Maria Saumell,
  • Rodrigo I. Silveira

摘要

We study a geometric facility location problem under imprecision. Given n unit segments on the real line, each with one of k colors, the goal is to place a point on each segment such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given segment of each color. We prove that if the input segments are pairwise disjoint, the problem can be solved in O(n) time, even for segments of arbitrary length. For overlapping segments, the problem becomes much more difficult. Nevertheless, we show that it can be solved in \(O(n \log ^2 n)\) O ( n log 2 n ) time when \(k=2\) k = 2 , by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard.