Sublinear Geometric Algorithms

Bernard Chazelle; Ding Liu; Avner Magen

Sublinear Geometric 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 dimen-sions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected 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)
Journal	Dagstuhl Seminar Proceedings
Volume	5291
State	Published - 2006
Externally published	Yes
Event	Sublinear Algorithms 2005 - Wadern, Germany Duration: Jul 17 2005 → Jul 22 2005

All Science Journal Classification (ASJC) codes

Software
Hardware and Architecture
Control and Systems Engineering

Cite this

@article{c9e98f9c2f7744349ec1b04ac65de573,

title = "Sublinear Geometric Algorithms",

abstract = "We initiate an investigation of sublinear algorithms for geometric problems in two and three dimen-sions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected 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.",

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

year = "2006",

language = "English (US)",

volume = "5291",

journal = "Dagstuhl Seminar Proceedings",

issn = "1862-4405",

}

TY - JOUR

T1 - Sublinear Geometric Algorithms

AU - Chazelle, Bernard

AU - Liu, Ding

AU - Magen, Avner

PY - 2006

Y1 - 2006

N2 - We initiate an investigation of sublinear algorithms for geometric problems in two and three dimen-sions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected 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 dimen-sions. We give optimal algorithms for intersection detection of convex polygons and polyhedra, point location in two-dimensional triangulations and Voronoi diagrams, and ray shooting in convex polyhedra, all of which run in expected 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.

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

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

M3 - Conference article

AN - SCOPUS:64549086683

SN - 1862-4405

VL - 5291

JO - Dagstuhl Seminar Proceedings

JF - Dagstuhl Seminar Proceedings

T2 - Sublinear Algorithms 2005

Y2 - 17 July 2005 through 22 July 2005

ER -

Sublinear Geometric Algorithms

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this