14.19.5 H.5. Path planning, etc.

Chapter Contents (Back)

Gouzenes, L.,
Strategies For Solving Collision-Free Trajectories Problems For Mobile And Manipulator Robots,
IJRR(3), No. 4, 1984, pp. 51-65. BibRef

Hopcroft, J.E., Schwartz, J.T., Sharir, M.,
On The Complexity Of Motion Planning For Multiple Independent Objects; Pspace-Hardness Of The ``Warehouseman'S Problem'',
IJRR(3), No. 4, 1984, pp. 76-88. BibRef

Toussaint, G.T.,
Movable Separability Of Sets,
CG(85), pp. 335-375. BibRef

Whitesides, S.H.,
Computational Geometry And Motion Planning,
CG(85), pp. 377-427. BibRef

Gilbert, E.G., Johnson, D.W.,
Distance Functions And Their Application To Robot Path Planning In The Presence Of Obstacles,
IEEE J. ROBOTICS AUTOMATION(1), 1985, pp. 21-30. BibRef

Crowley, J.L.,
Navigation For An Intelligent Mobile Robot,
IEEE J. ROBOTICS AUTOMATION(1), 1985, pp. 31-41. BibRef

O'Dunlaing, C., Yap, C.K.,
A ``Retraction'' Method For Planning The Motion Of A Disk,
J. ALGORITHMS(6), 1985, pp. 104-111. BibRef

Brooks, R.A., Lozano-Perez, T.,
A Subdivision Algorithm In Configuration Space For Findpath With Rotation,
T-SMC(15), 1985, pp. 224-233. BibRef

Chattergy, R.,
Some Heuristics For The Navigation Of A Robot,
IJRR(4), No. 1, 1985, pp. 59-66. BibRef

Hopcroft, J., Joseph, D., Whitesides, S.,
On The Movement Of Robot Arms In 2-Dimensional Bounded Regions,
SIAM JC(14), 1985, pp. 315-333. BibRef

Joseph, D.A., Plantinga, W.H.,
On The Complexity Of Reachability And Motion Planning Questions,
SCG(85), pp. 62-66. BibRef

Koutsou, A.,
A Geometric Reasoning System For Moving An Object While Maintaining Contact With Others,
SCG(85), pp. 67-74. BibRef

Kedem, K., Sharir, M.,
An Efficient Algorithm For Planning Collision-Free Translational Motion Of A Convex Polygonal Object In 2-Dimensional Space Amidst Polygonal Obstacles,
SCG(85), pp. 75-80. BibRef

de Rezende, P.J., Lee, D.T., Wu, Y.F.,
Rectilinear Shortest Paths With Rectangular Barriers,
SCG(85), pp. 204-213. BibRef

Chew, L.P.,
Planning The Shortest Path For A Disc In O(N(2)Log N) Time,
SCG(85), pp. 214-220. BibRef

Leven, D., Sharir, M.,
An Efficient And Simple Motion Planning Algorithm For A Ladder Moving In Two-Dimensional Space Amidst Polygonal Barriers,
SCG(85), pp. 221-227. BibRef

Rueb, K.D., Wong, A.K.C.,
A Hypergraph Representation Of Free Space For Path Planning,
CVPR(85), pp. 184-188. BibRef

Gilmore, J.F., Semeco, A.C.,
Autonomous Route Planning Through Non-Uniform Terrain,
CVPR(85), pp. 358-363. BibRef

Gilmore, J.F., Semeco, A.C.,
Terrain Navigation Through Knowledge-Based Route Planning,
IJCAI(85), pp. 1086-1088. BibRef

Buckley, C.E., Leifer, L.J.,
A Proximity Metric For Continuum Path Planning,
IJCAI(85), pp. 1096-1102. BibRef

Reif, J., Sharir, M.,
Motion Planning In The Presence Of Moving Obstacles,
SFCS(85), pp. 144-154. BibRef

Kambhampati, S., Davis, L.S.,
Multiresolution Path Planning For Mobile Robots,
IUW(85), pp. 421-432. BibRef

Iyengar, S.S., Jorgenson, C.C., Rao, S.V.N., Weisbin, C.R.,
Learned Navigation Paths For A Robot In Unexplored Terrain,
CAIA(85), pp. 148-155. BibRef

Turchan, M.P., Wong, A.K.C.,
Low Level Learning For A Mobile Robot: Environment Model Acquisition,
CAIA(85), pp. 156-161. BibRef

Pearson, G., Kuan, D.,
Mission Planning For An Autonomous Vehicle,
CAIA(85), pp. 162-167. BibRef

Nitao, J.J., Parodi, A.M.,
An Intelligent Pilot For An Autonomous Vehicle System,
CAIA(85), pp. 176-183. BibRef

Mark, D.M.,
Finding Simple Routes: ``Ease Of Description'' As An Objective Function In Automated Route Selection,
CAIA(85), pp. 577-587. BibRef

Shen, H.C., Signarowski, G.F.P.,
A Knowledge Representation For Roving Robots,
CAIA(85), pp. 621-628. BibRef

Streeter, L.A., Vitello, D., Wonsiewicz, S.A.,
How To Tell People Where To Go: Comparing Navigational Aids,
INTL. J. MAN-MACHINE STUDIES(22), 1985, pp. 549-562. BibRef

Haber, R.N.,
Toward A Theory Of The Perceived Spatial Layout Of Scenes,
CVGIP(31), 1985, pp. 282-321. BibRef

H'. Geometry

H'.1. General references

Proceedings Of The Symposium On Computational Geometry (Acm; Baltimore, Md,
JUNE 5-7, 1985).

Toussaint, G.,
Computational Geometry, North-Holland,
AMSTERDAM, 1985. BibRef

Forrest, R., Guibas, L., Nievergelt, J.,
Guest Eds., Special Issue On Computational Geometry,
TOG(3), No. 4, OCTOBER 1984, pp. 241-311. BibRef

Mehlhorn, K.,
Multi-Dimensional Searching And Computational Geometry, Springer,
BERLIN(85), pp. 1984. BibRef

Preparata, F.P., Shamos, M.I.,
Computational Geometry-An Introduction, Springer,
BERLIN(85), pp. 1985. BibRef

Chazelle, B., Guibas, L.J., Lee, D.T.,
The Power Of Geometric Duality,
BIT(25), 1985, pp. 76-90. BibRef

Devroye, L.,
Expected Time Analysis Of Algorithms In Computational Geometry,
CG(85), pp. 135-151. BibRef

Asano, T., Edahiro, M., Imai, H., Iri, M., Murota, K.,
Practical Use Of Bucketing Techniques In Computational Geometry,
CG(85), pp. 153-195. BibRef

Seidel, R.,
A Method For Proving Lower Bounds For Certain Geometric Properties,
CG(85), pp. 319-334. BibRef

Yao, A.C., Yao, F.F.,
A General Approach To D-Dimensional Geometric Queries,
STOC(85), pp. 163-168. BibRef

Fries, O., Mehlhorn, K., Naher, S.,
Dynamization Of Geometric Data Structures,
SCG(85), pp. 168-176. BibRef

Aggarwal, A., Chazelle, B., Guibas, L., O'Dunlaing, C., Yap, C.,
Parallel Computational Geometry,
SFCS(85), pp. 468-477. BibRef

Ruckle, W.H.,
Geometric Games And Their Applications, Pitman,
LONDON(85), pp. 1983. BibRef

Holroyd, F.C., Wilson, R.J.,
Geometrical Combinatorics, Pitman,
LONDON(85), pp. 1984. BibRef

H'.2. Distance

Edelsbrunner, H., Maurer, H.A.,
Finding Extreme Points In Three Dimensions And Solving The Post-Office Problem In The Plane,
IPL(21), 1985, pp. 39-47. BibRef

Lumelsky, V.J.,
On Fast Computation Of Distance Between Line Segments,
IPL(21), 1985, pp. 55-61. BibRef

Ching, Y.T., Lee, D.T.,
Finding The Diameter Of A Set Of Lines,
PR(18), 1985, pp. 249-255. BibRef

Melville, R.C.,
An Implementation Study Of Two Algorithms For The Minimum Spanning Circle Problem,
CG(85), pp. 267-294. BibRef

Clarkson, K.L.,
A Probabilistic Algorithm For The Post Office Problem,
STOC(85), pp. 175-184. BibRef

Sharir, M.,
Intersection And Closest-Pair Problems For A Set Of Planar Discs,
SIAM JC(14), 1985, pp. 448-468. BibRef

Houle, M.E., Toussaint, G.T.,
Computing The Width Of A Set,
SCG(85), pp. 1-7. BibRef

Widmayer, P., Wu, Y.F., Wong, C.K.,
Distance Problems In Computational Geometry With Fixed Orientations,
SCG(85), pp. 186-195. BibRef

Dehne, F., Noltemeier, H.,
A Computational Geometry Approach To Clustering Problems,
SCG(85), pp. 245-250. BibRef

Stout, Q.F.,
Pyramid Computer Solutions Of The Closest Pair Problem,
J. ALGORITHMS(6), 1985, pp. 200-212. BibRef

Edelsbrunner, H.,
Computing The Extreme Distances Between Two Convex Polygons,
J. ALGORITHMS (6), 1985, pp. 213-224. BibRef

Chang, R.C., Lee, R.C.T.,
On The Average Length Of Delaunay Triangulations,
BIT(24), 1984, pp. 269-273. BibRef

Bhattacharya, B.K., Toussaint, G.T.,
On Geometric Algorithms That Use The Furthest-Point Voronoi Diagram,
CG(85), pp. 43-61. BibRef

Lee, D.T.,
Relative Neighborhood Graphs In The L(1)-Metric,
PR(18), 1985, pp. 327-332. BibRef

Imai, H., Iri, M., Murota, K.,
Voronoi Diagrams In The Laguerre Geometry And Its Applications,
SIAM JC(14), 1985, pp. 93-105. BibRef

Guibas, L., Stolfi, J.,
Primitives For The Manipulation Of General Subdivisions And The Computation Of Voronoi Diagrams,
TOG(4), 1985, pp. 74-123. BibRef

Chazelle, B., Edelsbrunner, H.,
An Improved Algorithm For Constructing Kth-Order Voronoi Diagrams,
SCG(85), pp. 228-234. BibRef

Chew, L.P., Drysdale III, R.L.,
Voronoi Diagrams Based On Convex Distance Functions,
SCG(85), pp. 235-244. BibRef

Edelsbrunner, H., Seidel, R.,
Voronoi Diagrams And Arrangements,
SCG(85), pp. 251-262. BibRef

H'.3. Convexity, etc.

Toussaint, G.T.,
Complexity, Convexity, And Unimodality,
J. COMPUTER INFORMATION SCIENCES(13), 1984, pp. 197-217. BibRef

Akl, S.G.,
Optimal Parallel Algorithms For Selection, Sorting, And Computing Convex Hulls,
CG(85), pp. 1-22. BibRef

Avis, D., ElGindy, H., Seidel, R.,
Simple On-Line Algorithms For Convex Polygons,
CG(85), pp. 23-42. BibRef

Klee, V., Laskowski, M.C.,
Finding The Smallest Triangles Containing A Given Convex Polygon,
J. ALGORITHMS(6), 1985, pp. 359-375. BibRef

Orlawski, M.,
A Convex Hull Algorithm For Planar Simple Polygons,
PR(18), 1985, pp. 361-366. BibRef

Toussaint, G.T.,
A Historical Note On Convex Hull Finding Algorithms,
PRL(3), 1985, pp. 21-28. BibRef

McQueen, M.M., Toussaint, G.T.,
On The Ultimate Convex Hull Algorithm In Practice,
PRL(3), 1985, pp. 29-34. BibRef

Handley, C.C.,
Efficient Planar Convex Hull Algorithm,
IVC(3), 1985, pp. 29-35. BibRef

Boyce, J.E., Dobkin, D.P., Drysdale III, R.L., Guibas, L.J.,
Finding Extremal Polygons,
SIAM JC(14), 1985, pp. 134-147. BibRef

Swart, G.,
Finding The Convex Hull Facet By Facet,
J. ALGORITHMS(6), 1985, pp. 17-48. BibRef

Avis, D., Rappaport, D.,
Computing The Largest Empty Convex Subset Of A Set Of Points,
SCG(85), pp. 161-167. BibRef

Aggarwal, A., Booth, H., O'Rourke, J., Suri, S., Yap, C.K.,
Finding Minimal Convex Nested Polygons,
SCG(85), pp. 296-304. BibRef

Wood, D., Yap, C.K.,
Computing A Convex Skull Of An Orthogonal Polygon,
SCG(85), pp. 311-315. BibRef

Woo, T.C., Lee, H.C.,
On The Time Complexity For Circumscribing A Convex Polygon,
CVGIP(30), 1985, pp. 362-363. BibRef

O'Rourke, J.,
Counterexamples To A Minimal Circumscription Algorithm,
CVGIP(30), 1985, pp. 364-366. BibRef

Chazelle, B.,
On The Convex Layers Of A Planar Set,
T-IT(31), 1985, pp. 509-517. BibRef

Lee, D.T., Chen, I.M.,
Display Of Visible Edges Of A Set Of Convex Polygons,
CG(85), pp. 249-265. BibRef

Rappaport, D., Toussaint, G.T.,
A Simple Linear Hidden-Line Algorithm For Star-Shaped Polygons,
PRL(3), 1985, pp. 35-39. BibRef

Welzl, E.,
Constructing The Visibility Graph For N Line Segments In O(N(2)) Time,
IPL (20), 1985, pp. 167-171. BibRef

Asano, T., Asano, T., Guibas, L., Hershberger, J., Imai, H.,
Visibility-Polygon Search And Euclidean Shortest Paths,
SFCS(85), pp. 155-164. BibRef

H'.4. Intersection, containment, etc.

Sanz, J.L.C.,
A New Method For Computing Polygonal Masks In Image Processing Pipeline Architectures,
PR(18), 1985, pp. 241-247. BibRef

Rogers, D.F., Rybak, L.M.,
On An Efficient General Line-Clipping Algorithm,
CGA(5), No. 1, 1985, pp. 82-86. BibRef

Hsu, W.L.,
Maximum Weight Clique Algorithms For Circular-Arc Graphs And Circle Graphs,
SIAM JC(14), 1985, pp. 224-231. BibRef

Ottmann, T., Widmayer, P., Wood, D.,
A Fast Algorithm For The Boolean Masking Problem,
CVGIP(30), 1985, pp. 249-268. BibRef

Myers, E.W.,
An O(E Log E + I) Expected Time Algorithm For The Planar Segment Intersection Problem,
SIAM JC(14), 1985, pp. 625-637. BibRef

Kant, K.,
Finding Interferences Between Rectangular Paths,
T-COMP(34), 1985, pp. 1045-1049. BibRef

Burton, F.W., Kollias, V.J., Kollias, J.G.,
Consistency In Point-In-Polygon Tests,
COMPUTER J.(27), 1984, pp. 375-376. BibRef

Edahiro, M., Kokubo, I., Asano, T.,
A New Point-Location Algorithm And Its Practical Efficiency -Comparison With Existing Algorithms,
TOG(3), 1984, pp. 86-109. BibRef

Devroye, L.,
A Note On The Expected Time Required To Construct The Outer Layer,
IPL(20), 1985, pp. 255-257. BibRef

Willard, D.E.,
New Data Structures For Orthogonal Range Queries,
SIAM JC(14), 1985, pp. 232-253. BibRef

Vaidya, R.M.,
Space-Time Tradeoffs For Orthogonal Range Queries,
STOC(85), pp. 169-174. BibRef

Guting, R.H., Nurmi, O., Ottmann, T.,
The Direct Dominance Problem,
SCG(85), pp. 81-88. BibRef

Kirkpatrick, D.G., Seidel, R.,
Output-Size Sensitive Algorithms For Finding Maximal Vectors,
SCG(85), pp. 89-96. BibRef

Chazelle, B., Preparata, F.P.,
Halfspace Range Search: An Algorithmic Application Of K-Sets,
SCG(85), pp. 107-115. BibRef

Overmars, M.H.,
Range Searching In A Set Of Line Segments,
SCG(85), pp. 177-185. BibRef

Chazelle, B.,
Slimming Down Search Structures: A Functional Approach To Algorithm Design,
SFCS(85), pp. 165-174. BibRef

H'.5. Packing, layout

Assmann, S.F., Johnson, D.S., Kleitman, D.J., Leung, J.Y.T.,
On A Dual Version Of The One-Dimensional Bin Packing Problem,
J. ALGORITHMS(5), 1984, pp. 502-525. BibRef

Hofri, M.,
A Probabilistic Analysis Of The Next-Fit Bin Packing Algorithm,
J. ALGORITHMS(5), 1984, pp. 547-556. BibRef

Bruno, J.L., Downey, P.J.,
Probabilistic Bounds For Dual Bin-Packing,
ACTA INFORMATICA(22), 1985, pp. 333-345. BibRef

Hochbaum, D.S., Maass, W.,
Approximation Schemes For Covering And Packing Problems In Image Processing And Vlsi,
J. ACM(32), 1985, pp. 130-136. BibRef

Baker, B.S.,
A New Proof For The First-Fit Decreasing Bin-Packing Algorithm,
J. ALGORITHMS(6), 1985, pp. 49-70. BibRef

Lee, C.C., Lee, D.T.,
A Simple On-Line Bin-Packing Algorithm,
J. ACM(32), 1985, pp. 562-572. BibRef

Stockmeyer, L.,
Optimal Orientations Of Cells In Slicing Floorplan Designs,
INFORMATION CONTROL(57), 1983, pp. 91-101. BibRef

Lloyd, E.L., Ravi, S.S.,
One-Layer Routing Without Component Constraints,
J. COMPUTER SYSTEM SCIENCES(28), 1984, pp. 420-438. BibRef

Chiba, N., Nishizeki, T., Abe, S.,
A Linear Algorithm For Embedding Planar Graphs Using Pq-Trees,
J. COMPUTER SYSTEM SCIENCES(30), 1985, pp. 54-76. BibRef

Chiba, N., Onoguchi, K., Nishizeki, T.,
Drawing Plane Graphs Nicely,
ACTA INFORMATICA(22), 1985, pp. 187-201. BibRef

Miller, Z., Orlin, J.B.,
Np-Completeness For Minimizing Maximum Edge Length In Grid Embeddings,
J. ALGORITHMS(6), 1985, pp. 10-16. BibRef

Leiserson, C.E., Maley, F.M.,
Algorithms For Routing And Testing Routability Of Planar Vlsi Layouts,
STOC(85), pp. 69-78. BibRef

Raghavan, P., Thompson, C.D.,
Provably Good Routing In Graphs: Regular Arrays,
STOC(85), pp. 79-87. BibRef

Vijayan, G., Wigderson, A.,
Rectilinear Graphs And Their Embeddings,
SIAM JC(14), 1985, pp. 355-372. BibRef

Lipton, R.J., North, S.C., Sandberg, J.S.,
A Method For Drawing Graphs,
SCG(85), pp. 153-160. BibRef

Aggarwal, A., Klawe, M., Lichtenstein, D., Lincal, N., Wigderson, A.,
Multi-Layer Grid Embeddings,
SFCS(85), pp. 186-196. BibRef

Leighton, F.T.,
Complexity Issues In Vlsi: Optimal Layouts For The Shuffle-Exchange Graph And Other Networks, Mit Press, Cambridge,
MA(85), pp. 1983. BibRef

H'.6. Decomposition, partitioning

Brugner, G.,
Three-Triangle Tangram,
BIT(24), 1984, pp. 380-382. BibRef

Chazelle, B., Incerpi, J.,
Triangulation And Shape Complexity,
TOG(3), 1984, pp. 135-152. BibRef

Fournier, A., Montuno, D.Y.,
Triangulating Simple Polygons And Equivalent Problems,
TOG(3), 1984, pp. 153-174. BibRef

Tor, S.B., Middleditch, A.E.,
Convex Decomposition Of Simple Polygons,
TOG(3), 1984, pp. 244-265. BibRef

Chazelle, B., Dobkin, D.P.,
Optimal Convex Decompositions,
CG(85), pp. 63-133. BibRef

Keil, J.M., Sack, J.R.,
Minimum Decompositions Of Polygonal Objects,
CG(85), pp. 197-216. BibRef

Woo, T.C., Shin, S.Y.,
A Linear Time Algorithm For Triangulating A Point-Visible Polygon,
TOG(4), 1985, pp. 60-70. BibRef

Lubiw, A.,
Decomposing Polygonal Regions Into Convex Quadrilaterals,
SCG(85), pp. 97-106. BibRef

Gonzalez, T., Zheng, S.Q.,
Bounds For Partitioning Rectilinear Polygons,
SCG(85), pp. 281-287. BibRef

Lingas, A.,
On Partitioning Polygons,
SCG(85), pp. 288-295. BibRef

Megiddo, N.,
Partitioning With Two Lines In The Plane,
J. ALGORITHMS(6), 1985, pp. 430-433. BibRef

Avis, D.,
On The Partitionability Of Point Sets In Space,
SCG(85), pp. 116-120. BibRef

H'.7. Miscellaneous

Wood, D.,
The Contour Problem For Rectlinear Polygons,
IPL(19), 1984, pp. 229-236. BibRef

Wood, D.,
An Isothetic View Of Computational Geometry,
CG(85), pp. 429-459. BibRef

Fisher, J.C., Ruoff, D., Shilleto, J.,
Perpendicular Polygons,
AMER. MATH. MONTHLY(92), 1985, pp. 23-37. BibRef

Edelsbrunner, H.,
Finding Transversals For Sets Of Simple Geometric Figures,
THEORETICAL COMPUTER SCIENCE(35), 1985, pp. 55-69. BibRef

Goodman, J.E., Pollack, R.,
Modeling Planar Configurations,
SCG(85), pp. 121-124. BibRef

Chazelle, B.,
New Techniques For Computing Order Statistics In Euclidean Space,
SCG(85), pp. 125-134. BibRef

Chazelle, B., Guibas, L.J.,
Visibility And Intersection Problems In Plane Geometry,
SCG(85), pp. 135-146. BibRef

Wismath, S.K.,
Characterizing Bar Line-Of-Sight Graphs,
SCG(85), pp. 147-152. BibRef

Hoffmann, K., Mehlhorn, K., Rosenstiehl, P., Tarjan, R.E.,
Sorting Jordan Sequences In Linear Time,
SCG(85), pp. 196-203. BibRef

Culberson, J., Rawlins, G.,
Turtlegons: Generating Simple Polygons From Sequences Of Angles,
SCG(85), pp. 305-310. BibRef

Overmars, M.H., Welzl, E.,
The Complexity Of Cutting Paper,
SCG(85), pp. 316-321. BibRef

Atallah, M.J.,
On Symmetry Detection,
T-COMP(34), 1985, pp. 663-666. BibRef

Fleming, A.,
Analysis Of Uncertainties In A Structure Of Parts,
IJCAI(85), pp. 1113-1115. BibRef

Fischer, M.J., Paterson, M.S.,
Dynamic Monotone Priorities On Planar Sets,
SFCS(85), pp. 289-292. BibRef

Sharir, M., Levine, R.,
On Minima Of Functions, Intersection Patterns Of Curves, And Davenport-Schinzel Sequences,
SFCS(85), pp. 312-320. BibRef

Chapter on Rosenfeld Bibliography for 1985 continues in
I. Texture .

Last update:Jun 7, 2018 at 10:14:50