Sublinear geometrie algorithms

Bernard Chazelle; Ding Liu; Avner Magen

Sublinear geometrie algorithms

Research output: Contribution to journal › Conference article › peer-review

Abstract

We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional Delaunay triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.

Original language	English (US)
Pages (from-to)	531-540
Number of pages	10
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
State	Published - 2003
Event	35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 9 2003 → Jun 11 2003

All Science Journal Classification (ASJC) codes

Software

Keywords

Approximate shortest paths
Polyhedral intersection
Sublinear algorithms

Cite this

@article{d679449cf39c4e5d91347714b3e4f87b,

title = "Sublinear geometrie algorithms",

abstract = "We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional Delaunay triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.",

keywords = "Approximate shortest paths, Polyhedral intersection, Sublinear algorithms",

author = "Bernard Chazelle and Ding Liu and Avner Magen",

year = "2003",

language = "English (US)",

pages = "531--540",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "35th Annual ACM Symposium on Theory of Computing ; Conference date: 09-06-2003 Through 11-06-2003",

}

TY - JOUR

T1 - Sublinear geometrie algorithms

AU - Chazelle, Bernard

AU - Liu, Ding

AU - Magen, Avner

PY - 2003

Y1 - 2003

N2 - We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional Delaunay triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.

AB - We initiate an investigation of sublinear algorithms for geometric problems in two and three dimensions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional Delaunay triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in time O(√n), where n is the size of the input. We also provide sublinear solutions for the approximate evaluation of the volume of a convex polytope and the length of the shortest path between two points on the boundary.

KW - Approximate shortest paths

KW - Polyhedral intersection

KW - Sublinear algorithms

UR - http://www.scopus.com/inward/record.url?scp=0038446906&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038446906&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0038446906

SN - 0734-9025

SP - 531

EP - 540

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 35th Annual ACM Symposium on Theory of Computing

Y2 - 9 June 2003 through 11 June 2003

ER -

Sublinear geometrie algorithms

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Other files and links

Fingerprint

Cite this