Draft:Klee's algorithm - Revision history

TakuyaMurata: #redirect Klee's measure problem; the algorithm is unreferenced so I don't think it can be merged into the existing article

2025-06-15T06:41:57Z

#redirect Klee's measure problem; the algorithm is unreferenced so I don't think it can be merged into the existing article

← Previous revision		Revision as of 06:41, 15 June 2025
Line 1:		Line 1:
			#redirect [[Klee's measure problem]]
	{{AFC submission\|d\|nn\|u=David of Earth\|ns=118\|decliner=Felix QW\|declinets=20240626115055\|reason2=v\|ts=20240409075516}} <!-- Do not remove this line! -->

	{{AFC comment\|1=The sections on "Logical error in the original" and the Javascript implementation are unsourced. Apart from the bullet-listed description of the algorithm, the page [[Klee's measure problem]] already contains the verifiable, encyclopedic content of this draft. As the latest reference provided here is from 1978, it is unclear currently that this topic is notable separately from [[Klee's measure problem]], which puts it in relevant context. [[User:Felix QW\|Felix QW]] ([[User talk:Felix QW\|talk]]) 11:50, 26 June 2024 (UTC)}}

	{{AFC comment\|The correct to the original is my own work. How do you suggest that I source it? [[User:David of Earth\|David of Earth]] ([[User talk:David of Earth\|talk]]) 08:18, 18 December 2024 (UTC)}}

	{{AFC comment\|I'm adding another comment in the hope someone can answer my question. [[User:David of Earth\|David of Earth]] ([[User talk:David of Earth\|talk]]) 03:34, 5 May 2025 (UTC)}}


	----

	{{Short description\|Algorithm for the length of a union of intervals}}
	{{Draft topics\|mathematics}}
	{{AfC topic\|stem}}

	Framed as an open research problem published in 1977 in ''The American Mathematical Monthly'',<ref>{{cite journal
	\|first1=Victor
	\|last1=Klee
	\|author-link1=Victor Klee
	\|year=1977
	\|title=Can the measure of <math>\cup[a_i, b_i]</math> be computed in less than <math>O(n \log n)</math> steps?
	\|journal=[[American Mathematical Monthly]]
	\|volume=84
	\|issue=4
	\|pages=284–285
	\|mr=0436661
	\|doi=10.2307/2318871
	\|jstor=2318871
	}}</ref> Victor Klee presented a challenge to the journal's readers to find an algorithm to compute the measure of the union of a set of intervals that would be more efficient than sorting the interval endpoints and sequentially adding the resulting lengths together. Klee then provided an algorithm in pseudocode that performs the sorting and summation as a baseline solution for this problem with a complexity of <math>O(n \log n)</math>. This complexity was later proven to be optimal in 1978 by Michael Freman and Bruce Weide.<ref>*{{cite journal
	\|first1=Michael L.
	\|last1=Fredman
	\|author-link1=Michael Fredman
	\|first2=Bruce
	\|last2=Weide
	\|year=1978
	\|title=The complexity of computing the measure of <math>\cup[a_i, b_i]</math>
	\|journal=[[Communications of the ACM]]
	\|volume=21 \|issue=7
	\|pages=540–544
	\|mr=0495193
	\|doi=10.1145/359545.359553
	\|s2cid=16493364
	\|doi-access=free
	}}</ref>

	As an additional challenge, Klee invited the readers to consider the problem in multiple dimensions and how efficiently someone could solve the complexity of finding a disjoint set of d-dimensional intervals, reducing that set to the minimum number of intervals possible, and computing the measure of their union. This last question was eventually labeled [[Klee's measure problem]].

	== Algorithm ==

	# Separate the endpoint pairs for each interval and tag if each endpoint was on the left or the right.
	# Sort the individual endpoints in ascending order of value, with the additional condition that left endpoints are before right endpoints when two endpoint values are the same. (This changes any partially overlapping intervals into a series of nested ones.)
	# Iterate through the sorted endpoints, keeping track of the interval nesting count and recording just the outermost interval of each nesting.
	# Add up the measures of each of the resulting set of disjointed intervals.

	=== Logical error in the original ===

	The original pseudocode had the following lines inside of the loop through the endpoints:

	<math>EXCESS = EXCESS + t_i</math>
	if <math>EXCESS = 1</math> then <math>m = m + 1</math> and <math>c_m = e_i</math>
	if <math>EXCESS = 0</math> then <math>d_m = e_i</math>

	where <math>EXCESS</math> is the interval nesting count, <math>i</math> is the current endpoint index, <math>t_i</math> = +1 for left endpoints and -1 for right endpoints, <math>e_i</math> is the current endpoint value, <math>m</math> is the index of the current interval for the new set, and
	<math>c_m</math> and <math>d_m</math> are the start and end of the current interval for the new set, respectively. This code incorrectly jumps ahead <math>m</math> at the right endpoint of the second outermost interval and uses that endpoint as the left endpoint of the next recorded interval.

	To fix this problem, the pseudocode could be rewritten as follows:

	if <math>EXCESS = 0</math> then <math>m = m + 1</math> and <math>c_m = e_i</math>
	<math>EXCESS = EXCESS + t_i</math>
	if <math>EXCESS = 0</math> then <math>d_m = e_i</math>

	This way, the first line only triggers before the first endpoint of a nested set of endpoints and the second line only triggers after the end of the last endpoint of such a set.

	=== Javascript implementation ===

	<syntaxhighlight lang="javascript" line>
	function measureOfUnion(intervals = []) {
	// the input is expected to be an array of intervals,
	// with each interval being a 2-element array
	const endpoints = [];
	for (let interval of intervals) {
	endpoints.push({v: interval[0], nestingChange: +1});
	endpoints.push({v: interval[1], nestingChange: -1});
	}
	endpoints.sort(endpointSort);
	const disjointIntervals = [];
	let nestingLevel = 0;
	let currentInterval;
	for (let endpoint of endpoints) {
	if (nestingLevel === 0) {
	currentInterval = [endpoint.v];
	disjointIntervals.push(currentInterval);
	}
	nestingLevel += endpoint.nestingChange;
	if (nestingLevel === 0)
	currentInterval.push(endpoint.v);
	}
	let measure = 0;
	for (let interval of disjointIntervals) {
	measure += interval[1] - interval[0];
	}
	return measure;
	}

	function endpointSort(a, b) {
	// normal expression for ascending order
	if (a.v != b.v) return a.v - b.v;
	// swap endpoints if the first one ends an interval
	if (a.nestingChange == -1) return +1;
	// otherwise, stay in this order
	return -1;
	}
	</syntaxhighlight>

	== References ==
	<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
	{{reflist}}

David of Earth: Refreshed my inquiry

2025-05-05T03:34:43Z

Refreshed my inquiry

← Previous revision		Revision as of 03:34, 5 May 2025
Line 4:		Line 4:

	{{AFC comment\|The correct to the original is my own work. How do you suggest that I source it? [[User:David of Earth\|David of Earth]] ([[User talk:David of Earth\|talk]]) 08:18, 18 December 2024 (UTC)}}		{{AFC comment\|The correct to the original is my own work. How do you suggest that I source it? [[User:David of Earth\|David of Earth]] ([[User talk:David of Earth\|talk]]) 08:18, 18 December 2024 (UTC)}}

			{{AFC comment\|I'm adding another comment in the hope someone can answer my question. [[User:David of Earth\|David of Earth]] ([[User talk:David of Earth\|talk]]) 03:34, 5 May 2025 (UTC)}}


	----		----

David of Earth: Where can I put an original correction?

2024-12-18T08:19:25Z

Where can I put an original correction?

← Previous revision		Revision as of 08:19, 18 December 2024
Line 2:		Line 2:

	{{AFC comment\|1=The sections on "Logical error in the original" and the Javascript implementation are unsourced. Apart from the bullet-listed description of the algorithm, the page [[Klee's measure problem]] already contains the verifiable, encyclopedic content of this draft. As the latest reference provided here is from 1978, it is unclear currently that this topic is notable separately from [[Klee's measure problem]], which puts it in relevant context. [[User:Felix QW\|Felix QW]] ([[User talk:Felix QW\|talk]]) 11:50, 26 June 2024 (UTC)}}		{{AFC comment\|1=The sections on "Logical error in the original" and the Javascript implementation are unsourced. Apart from the bullet-listed description of the algorithm, the page [[Klee's measure problem]] already contains the verifiable, encyclopedic content of this draft. As the latest reference provided here is from 1978, it is unclear currently that this topic is notable separately from [[Klee's measure problem]], which puts it in relevant context. [[User:Felix QW\|Felix QW]] ([[User talk:Felix QW\|talk]]) 11:50, 26 June 2024 (UTC)}}

			{{AFC comment\|The correct to the original is my own work. How do you suggest that I source it? [[User:David of Earth\|David of Earth]] ([[User talk:David of Earth\|talk]]) 08:18, 18 December 2024 (UTC)}}

	----		----

TakuyaMurata: TakuyaMurata moved page Draft:Klee's Algorithm to Draft:Klee's algorithm: Lowercase

2024-07-03T20:20:07Z

TakuyaMurata moved page Draft:Klee's Algorithm to Draft:Klee's algorithm: Lowercase

← Previous revision	Revision as of 20:20, 3 July 2024
(No difference)

Felix QW: Declining submission: nn - Submission is about a topic not yet shown to meet general notability guidelines (be more specific if possible) and v - Submission is improperly sourced (AFCH)

2024-06-26T11:50:55Z

Declining submission: nn - Submission is about a topic not yet shown to meet general notability guidelines (be more specific if possible) and v - Submission is improperly sourced (AFCH)

← Previous revision		Revision as of 11:50, 26 June 2024
Line 1:		Line 1:
			{{AFC submission\|d\|nn\|u=David of Earth\|ns=118\|decliner=Felix QW\|declinets=20240626115055\|reason2=v\|ts=20240409075516}} <!-- Do not remove this line! -->

			{{AFC comment\|1=The sections on "Logical error in the original" and the Javascript implementation are unsourced. Apart from the bullet-listed description of the algorithm, the page [[Klee's measure problem]] already contains the verifiable, encyclopedic content of this draft. As the latest reference provided here is from 1978, it is unclear currently that this topic is notable separately from [[Klee's measure problem]], which puts it in relevant context. [[User:Felix QW\|Felix QW]] ([[User talk:Felix QW\|talk]]) 11:50, 26 June 2024 (UTC)}}

			----

	{{Short description\|Algorithm for the length of a union of intervals}}		{{Short description\|Algorithm for the length of a union of intervals}}
	{{Draft topics\|mathematics}}		{{Draft topics\|mathematics}}
	{{AfC topic\|stem}}		{{AfC topic\|stem}}
	{{AfC submission\|\|\|ts=20240409075516\|u=David of Earth\|ns=118}}
	{{AfC submission\|t\|\|ts=20240409074923\|u=David of Earth\|ns=118\|demo=}}<!-- Important, do not remove this line before article has been created. -->

	Framed as an open research problem published in 1977 in ''The American Mathematical Monthly'',<ref>{{cite journal		Framed as an open research problem published in 1977 in ''The American Mathematical Monthly'',<ref>{{cite journal

David of Earth: Submitting using AfC-submit-wizard

2024-04-09T07:55:16Z

Submitting using AfC-submit-wizard

← Previous revision		Revision as of 07:55, 9 April 2024
Line 1:		Line 1:
			{{Short description\|Algorithm for the length of a union of intervals}}
			{{Draft topics\|mathematics}}
			{{AfC topic\|stem}}
			{{AfC submission\|\|\|ts=20240409075516\|u=David of Earth\|ns=118}}
	{{AfC submission\|t\|\|ts=20240409074923\|u=David of Earth\|ns=118\|demo=}}<!-- Important, do not remove this line before article has been created. -->		{{AfC submission\|t\|\|ts=20240409074923\|u=David of Earth\|ns=118\|demo=}}<!-- Important, do not remove this line before article has been created. -->

David of Earth: Initial page draft creation

2024-04-09T07:50:20Z

Initial page draft creation

New page

{{AfC submission|t||ts=20240409074923|u=David of Earth|ns=118|demo=}}

Framed as an open research problem published in 1977 in ''The American Mathematical Monthly'',<ref>{{cite journal
|first1=Victor
|last1=Klee
|author-link1=Victor Klee
|year=1977
|title=Can the measure of <math>\cup[a_i, b_i]</math> be computed in less than <math>O(n \log n)</math> steps?
|journal=[[American Mathematical Monthly]]
|volume=84
|issue=4
|pages=284–285
|mr=0436661
|doi=10.2307/2318871
|jstor=2318871
}}</ref> Victor Klee presented a challenge to the journal's readers to find an algorithm to compute the measure of the union of a set of intervals that would be more efficient than sorting the interval endpoints and sequentially adding the resulting lengths together. Klee then provided an algorithm in pseudocode that performs the sorting and summation as a baseline solution for this problem with a complexity of <math>O(n \log n)</math>. This complexity was later proven to be optimal in 1978 by Michael Freman and Bruce Weide.<ref>*{{cite journal
|first1=Michael L.
|last1=Fredman
|author-link1=Michael Fredman
|first2=Bruce
|last2=Weide
|year=1978
|title=The complexity of computing the measure of <math>\cup[a_i, b_i]</math>
|journal=[[Communications of the ACM]]
|volume=21 |issue=7
|pages=540–544
|mr=0495193
|doi=10.1145/359545.359553
|s2cid=16493364
|doi-access=free
}}</ref>

As an additional challenge, Klee invited the readers to consider the problem in multiple dimensions and how efficiently someone could solve the complexity of finding a disjoint set of d-dimensional intervals, reducing that set to the minimum number of intervals possible, and computing the measure of their union. This last question was eventually labeled [[Klee's measure problem]].

== Algorithm ==

# Separate the endpoint pairs for each interval and tag if each endpoint was on the left or the right.
# Sort the individual endpoints in ascending order of value, with the additional condition that left endpoints are before right endpoints when two endpoint values are the same. (This changes any partially overlapping intervals into a series of nested ones.)
# Iterate through the sorted endpoints, keeping track of the interval nesting count and recording just the outermost interval of each nesting.
# Add up the measures of each of the resulting set of disjointed intervals.

=== Logical error in the original ===

The original pseudocode had the following lines inside of the loop through the endpoints:

<math>EXCESS = EXCESS + t_i</math>
if <math>EXCESS = 1</math> then <math>m = m + 1</math> and <math>c_m = e_i</math>
if <math>EXCESS = 0</math> then <math>d_m = e_i</math>

where <math>EXCESS</math> is the interval nesting count, <math>i</math> is the current endpoint index, <math>t_i</math> = +1 for left endpoints and -1 for right endpoints, <math>e_i</math> is the current endpoint value, <math>m</math> is the index of the current interval for the new set, and
<math>c_m</math> and <math>d_m</math> are the start and end of the current interval for the new set, respectively. This code incorrectly jumps ahead <math>m</math> at the right endpoint of the second outermost interval and uses that endpoint as the left endpoint of the next recorded interval.

To fix this problem, the pseudocode could be rewritten as follows:

if <math>EXCESS = 0</math> then <math>m = m + 1</math> and <math>c_m = e_i</math>
<math>EXCESS = EXCESS + t_i</math>
if <math>EXCESS = 0</math> then <math>d_m = e_i</math>

This way, the first line only triggers before the first endpoint of a nested set of endpoints and the second line only triggers after the end of the last endpoint of such a set.

=== Javascript implementation ===

<syntaxhighlight lang="javascript" line>
function measureOfUnion(intervals = []) {
// the input is expected to be an array of intervals,
// with each interval being a 2-element array
const endpoints = [];
for (let interval of intervals) {
endpoints.push({v: interval[0], nestingChange: +1});
endpoints.push({v: interval[1], nestingChange: -1});
}
endpoints.sort(endpointSort);
const disjointIntervals = [];
let nestingLevel = 0;
let currentInterval;
for (let endpoint of endpoints) {
if (nestingLevel === 0) {
currentInterval = [endpoint.v];
disjointIntervals.push(currentInterval);
}
nestingLevel += endpoint.nestingChange;
if (nestingLevel === 0)
currentInterval.push(endpoint.v);
}
let measure = 0;
for (let interval of disjointIntervals) {
measure += interval[1] - interval[0];
}
return measure;
}

function endpointSort(a, b) {
// normal expression for ascending order
if (a.v != b.v) return a.v - b.v;
// swap endpoints if the first one ends an interval
if (a.nestingChange == -1) return +1;
// otherwise, stay in this order
return -1;
}
</syntaxhighlight>

== References ==

{{reflist}}

← Previous revision		Revision as of 11:50, 26 June 2024
Line 1:		Line 1:
			{{AFC submission\|d\|nn\|u=David of Earth\|ns=118\|decliner=Felix QW\|declinets=20240626115055\|reason2=v\|ts=20240409075516}} <!-- Do not remove this line! -->

			{{AFC comment\|1=The sections on "Logical error in the original" and the Javascript implementation are unsourced. Apart from the bullet-listed description of the algorithm, the page [[Klee's measure problem]] already contains the verifiable, encyclopedic content of this draft. As the latest reference provided here is from 1978, it is unclear currently that this topic is notable separately from [[Klee's measure problem]], which puts it in relevant context. [[User:Felix QW\|Felix QW]] ([[User talk:Felix QW\|talk]]) 11:50, 26 June 2024 (UTC)}}

			----

	{{Short description\|Algorithm for the length of a union of intervals}}		{{Short description\|Algorithm for the length of a union of intervals}}
	{{Draft topics\|mathematics}}		{{Draft topics\|mathematics}}
	{{AfC topic\|stem}}		{{AfC topic\|stem}}
	{{AfC submission\|\|\|ts=20240409075516\|u=David of Earth\|ns=118}}
	{{AfC submission\|t\|\|ts=20240409074923\|u=David of Earth\|ns=118\|demo=}}<!-- Important, do not remove this line before article has been created. -->

	Framed as an open research problem published in 1977 in ''The American Mathematical Monthly'',<ref>{{cite journal		Framed as an open research problem published in 1977 in ''The American Mathematical Monthly'',<ref>{{cite journal