Seventeen lines and one-hundred-and-one points

Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationAlgorithms - ESA 2003
Subtitle of host publication11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings
EditorsG. Di Battista, U. Zwick
PublisherSpringer
Pages527-531
ISBN (Electronic)978-3-540-39658-1
ISBN (Print)978-3-540-20064-2
DOIs
Publication statusPublished - 2003
Event11th Annual European Symposium  on Algorithms, ESA 2003 - Budapest, Hungary
Duration: 16 Sep 200319 Sep 2003
Conference number: 11

Publication series

NameLecture Notes in Computer Science
Volume2832
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th Annual European Symposium  on Algorithms, ESA 2003
Abbreviated titleESA
CountryHungary
CityBudapest
Period16/09/0319/09/03

Keywords

  • METIS-213364

Fingerprint Dive into the research topics of 'Seventeen lines and one-hundred-and-one points'. Together they form a unique fingerprint.

Cite this