Seventeen lines and one-hundred-and-one points

Gerhard Woeginger

doi:10.1007/978-3-540-39658-1_48

Seventeen lines and one-hundred-and-one points

Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Downloads (Pure)

Abstract

We investigate a curious problem from additive number theory: Given two positive integers S and Q, does there exist a sequence of positive integers that add up to S and whose squares add up to Q? We show that this problem can be solved in time polynomially bounded in the logarithms of S and Q.

As a consequence, also the following question can be answered in polynomial time: For given numbers n and m, do there exist n lines in the Euclidean plane with exactly m points of intersection?

Original language	English
Title of host publication	Algorithms - ESA 2003
Subtitle of host publication	11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings
Editors	G. Di Battista, U. Zwick
Publisher	Springer
Pages	527-531
ISBN (Electronic)	978-3-540-39658-1
ISBN (Print)	978-3-540-20064-2
DOIs	https://doi.org/10.1007/978-3-540-39658-1_48
Publication status	Published - 2003
Event	11th Annual European Symposium on Algorithms, ESA 2003 - Budapest, Hungary Duration: 16 Sept 2003 → 19 Sept 2003 Conference number: 11

Publication series

Name	Lecture Notes in Computer Science
Volume	2832
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th Annual European Symposium on Algorithms, ESA 2003
Abbreviated title	ESA
Country/Territory	Hungary
City	Budapest
Period	16/09/03 → 19/09/03

Keywords

METIS-213364

Access to Document

10.1007/978-3-540-39658-1_48

Cite this

@inproceedings{60f9e8590b194edeb88d5a5f90d161f2,

title = "Seventeen lines and one-hundred-and-one points",

abstract = "We investigate a curious problem from additive number theory: Given two positive integers S and Q, does there exist a sequence of positive integers that add up to S and whose squares add up to Q? We show that this problem can be solved in time polynomially bounded in the logarithms of S and Q. As a consequence, also the following question can be answered in polynomial time: For given numbers n and m, do there exist n lines in the Euclidean plane with exactly m points of intersection?",

keywords = "METIS-213364",

author = "Gerhard Woeginger",

year = "2003",

doi = "10.1007/978-3-540-39658-1\_48",

language = "English",

isbn = "978-3-540-20064-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "527--531",

editor = "\{Di Battista\}, G. and U. Zwick",

booktitle = "Algorithms - ESA 2003",

address = "Germany",

note = "11th Annual European Symposium on Algorithms, ESA 2003, ESA ; Conference date: 16-09-2003 Through 19-09-2003",

}

Woeginger, G 2003, Seventeen lines and one-hundred-and-one points. in G Di Battista & U Zwick (eds), Algorithms - ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings. Lecture Notes in Computer Science, vol. 2832, Springer, pp. 527-531, 11th Annual European Symposium on Algorithms, ESA 2003, Budapest, Hungary, 16/09/03. https://doi.org/10.1007/978-3-540-39658-1_48

Seventeen lines and one-hundred-and-one points. / Woeginger, Gerhard.
Algorithms - ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings. ed. / G. Di Battista; U. Zwick. Springer, 2003. p. 527-531 (Lecture Notes in Computer Science; Vol. 2832).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Seventeen lines and one-hundred-and-one points

AU - Woeginger, Gerhard

N1 - Conference code: 11

PY - 2003

Y1 - 2003

N2 - We investigate a curious problem from additive number theory: Given two positive integers S and Q, does there exist a sequence of positive integers that add up to S and whose squares add up to Q? We show that this problem can be solved in time polynomially bounded in the logarithms of S and Q. As a consequence, also the following question can be answered in polynomial time: For given numbers n and m, do there exist n lines in the Euclidean plane with exactly m points of intersection?

AB - We investigate a curious problem from additive number theory: Given two positive integers S and Q, does there exist a sequence of positive integers that add up to S and whose squares add up to Q? We show that this problem can be solved in time polynomially bounded in the logarithms of S and Q. As a consequence, also the following question can be answered in polynomial time: For given numbers n and m, do there exist n lines in the Euclidean plane with exactly m points of intersection?

KW - METIS-213364

U2 - 10.1007/978-3-540-39658-1_48

DO - 10.1007/978-3-540-39658-1_48

M3 - Conference contribution

SN - 978-3-540-20064-2

T3 - Lecture Notes in Computer Science

SP - 527

EP - 531

BT - Algorithms - ESA 2003

A2 - Di Battista, G.

A2 - Zwick, U.

PB - Springer

T2 - 11th Annual European Symposium on Algorithms, ESA 2003

Y2 - 16 September 2003 through 19 September 2003

ER -

Seventeen lines and one-hundred-and-one points

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this