DEEPAK.SURTI
  • Home
  • Blog
  • Mobile Apps
  • Open Source
  • Cool 3D Demos
  • About

Landmarks Web App (ITA Archived Puzzle, Analyzed)

5/24/2011

0 Comments

 
Picture
Please refer to the landmarks web app problem on this page.

Analysis

The key part to solve here is to pick the nearby landmarks. As such we need to define what nearby means. Since each landmark’s latitutde and longitude are defined, we can define for a given landmark lm, whose latitude and longitude are \(lm_{lat}\)and \(lm_{long}\) respectively; a nearby landmark nlm with latitude and longitude \(nlm_{lat}\) and \(nlm_{long}\) such that:

The nearest \(nlm_{lat} < lm_{lat}\)OR

The nearest \(nlm_{lat} > lm_{lat}\) OR

The nearest \(nlm_{long} < lm_{long}\) OR

The nearest \(nlm_{long} > lm_{long}\)

In other words, the nearest landmark in any direction to the given landmark assuming the given landmark as a center. If we can now think of a landmkark as a vertex on a graph, then the neighboring vertexes of a given landmark will be those landmarks that satisfy the above definition.

Algorithm

Build a B-Tree where key is latitude and another where key is longitude. Now do a inorder traversal of this BTree while adding a landmark as a key to a hash table and its nearest landmarkes as values. Then given a landmark, we just look up in the hash table to find the nearest landmarks.

Implementation

In order to make the web application responsive, it would be nice to load the page with a javscript hashtable of landmarks and its nearby landmarks.
0 Comments

Your comment will be posted after it is approved.


Leave a Reply.

    Picture

    Me

    I am a 3D graphics software engineer.

    profile for dmsurti at Stack Overflow, Q&A for professional and enthusiast programmers

    Archives

    December 2011
    November 2011
    October 2011
    September 2011
    August 2011
    July 2011
    June 2011
    May 2011
    April 2011
    August 2010
    January 2010
    December 2009
    September 2009
    August 2009

    Categories

    All
    Automator
    Books
    Code
    Continuations
    Css
    Drakma
    Education
    Express Card
    External Drive
    Html
    Ita
    Learning
    Life
    Lisp
    Mac
    Macros
    Mercurial
    Productivity
    Puzzle
    Reading
    Rss
    Simplicity
    Sudoku
    Work

    RSS Feed

    Picture
    me @ delicious
Powered by Create your own unique website with customizable templates.
  • Home
  • Blog
  • Mobile Apps
  • Open Source
  • Cool 3D Demos
  • About