Health & Environmental Research Online (HERO)


Print Feedback Export to File
2272831 
Journal Article 
On a class of O(n(2)) problems in computational geometry 
Gajentaan, A; Overmars, MH 
2012 
Yes 
Computational Geometry
ISSN: 0925-7721 
45 
4 
140-152 
WOS:000300479400002 
There are many problems in computational geometry for which the best know algorithms take time Theta(n(2)) (or more) in the worst case while only very low lower bounds are known. In this paper we describe a large class of problems for which we prove that they are all at least as difficult as the following base problem 3SUM: Given a set S of n integers, are there three elements of S that sum up to 0. We call such problems 3SUM-hard. The best known algorithm for the base problem takes Theta(n(2)) time. The class of 3SUM-hard problems includes problems like: Given a set of lines in the plane, are there three that meet in a point?: or: Given a set of triangles in the plane, does their union have a hole? Also certain visibility and motion planning problems are shown to be in the class. Although this does not prove a lower bound for these problems, there is no hope of obtaining o(n(2)) solutions for them unless we can improve the solution for the base problem. (C) 1995 Published by Elsevier B.V. Reprinted with permission from Computational Geometry, Vol. 5, No. 3, October 1995, Gajentaan, Overmars, 'On a class of O(n(2)) problems in computational geometry', pages 165-185. Published by Elsevier B.V. All rights reserved. 
Incidence; Separator; Covering; Visibility; Motion planning; 3sum-hard problems